Reference : Efficient Symbolic Representation of Convex Polyhedra in High-Dimensional Spaces
Scientific congresses and symposiums : Paper published in a journal
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/227564
Efficient Symbolic Representation of Convex Polyhedra in High-Dimensional Spaces
English
Boigelot, Bernard mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique >]
Mainz, Isabelle mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore) >]
2018
Lecture Notes in Computer Science
Springer
Yes
No
International
0302-9743
Berlin
Germany
16th International Symposium on Automated Technology for Verification and Analysis
from 7-10-2018 to 10-10-2018
Los Angeles
USA
[en] convex polyhedra ; symbolic representation
[en] This work is aimed at developing an efficient data structure for representing symbolically convex polyhedra. We introduce an original data structure, the Decomposed Convex Polyhedron (DCP), that is closed under intersection and linear transformations, and allows to check inclusion, equality, and emptiness. The main feature of DCPs lies in their ability to represent concisely polyhedra that can be expressed as combinations of simpler sets, which can overcome combinatorial explosion in high dimensional spaces. DCPs also have the advantage of being reducible into a canonical form, which makes them efficient for representing simple sets constructed by long sequences of manipulations, such as those handled by state-space exploration tools. Their practical efficiency has been evaluated with the help of a prototype implementation, with promising results.
http://hdl.handle.net/2268/227564
10.1007/978-3-030-01090-4_17

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
paper.pdfAuthor preprint379.93 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.