文章基本信息

标题：Implicit Real Vector Automata
本地全文：下载
作者：Bernard Boigelot ; Julien Brusten ; Jean-François Degbomont 等
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2010
卷号：39
页码：63-76
DOI：10.4204/EPTCS.39.5
出版社：Open Publishing Association
摘要：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.