Implicit Real Vector Automata
This paper addresses the symbolic representation of non-convex real polyhedra, i.e., sets of real vectors satisfying arbitrary Boolean combinations of linear constraints. We develop an original data structure for representing such sets, based on an implicit and concise encoding of a known structure,...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2010-10-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1011.0221v1 |
| _version_ | 1818754299151253504 |
|---|---|
| author | Jean-François Degbomont Julien Brusten Bernard Boigelot |
| author_facet | Jean-François Degbomont Julien Brusten Bernard Boigelot |
| author_sort | Jean-François Degbomont |
| collection | DOAJ |
| description | This paper addresses the symbolic representation of non-convex real polyhedra, i.e., sets of real vectors satisfying arbitrary Boolean combinations of linear constraints. We develop an original data structure for representing such sets, based on an implicit and concise encoding of a known structure, the Real Vector Automaton. The resulting formalism provides a canonical representation of polyhedra, is closed under Boolean operators, and admits an efficient decision procedure for testing the membership of a vector. |
| first_indexed | 2024-12-18T05:21:02Z |
| format | Article |
| id | doaj.art-0833100e19e2474f92ae35ab04c8d8d2 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-18T05:21:02Z |
| publishDate | 2010-10-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-0833100e19e2474f92ae35ab04c8d8d22022-12-21T21:19:40ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802010-10-0139Proc. INFINITY 2010637610.4204/EPTCS.39.5Implicit Real Vector AutomataJean-François DegbomontJulien BrustenBernard BoigelotThis paper addresses the symbolic representation of non-convex real polyhedra, i.e., sets of real vectors satisfying arbitrary Boolean combinations of linear constraints. We develop an original data structure for representing such sets, based on an implicit and concise encoding of a known structure, the Real Vector Automaton. The resulting formalism provides a canonical representation of polyhedra, is closed under Boolean operators, and admits an efficient decision procedure for testing the membership of a vector.http://arxiv.org/pdf/1011.0221v1 |
| spellingShingle | Jean-François Degbomont Julien Brusten Bernard Boigelot Implicit Real Vector Automata Electronic Proceedings in Theoretical Computer Science |
| title | Implicit Real Vector Automata |
| title_full | Implicit Real Vector Automata |
| title_fullStr | Implicit Real Vector Automata |
| title_full_unstemmed | Implicit Real Vector Automata |
| title_short | Implicit Real Vector Automata |
| title_sort | implicit real vector automata |
| url | http://arxiv.org/pdf/1011.0221v1 |
| work_keys_str_mv | AT jeanfrancoisdegbomont implicitrealvectorautomata AT julienbrusten implicitrealvectorautomata AT bernardboigelot implicitrealvectorautomata |