2006 | OriginalPaper | Chapter
Computing Affine Hulls over and from Sets Represented by Number Decision Diagrams
Author : Louis Latour
Published in: Implementation and Application of Automata
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Number Decision Diagrams (NDD) are finite automata representing sets of integer vectors and have recently been proposed as an efficient data structure for representing sets definable in Presburger arithmetic. In this context, some work has been done in order to generate formulas or sets of generators from the NDDs. Taking another step in this direction, this paper present algorithms that takes as input an NDD and computes the affine hull over
${\mathbb Q}$
or over
${\mathbb Z}$
of the set represented by the NDD, i.e., the smallest set defined by a conjunction of equations or by a conjunction of equations and congruence relations that includes the set represented by the NDD. Our algorithms run in time
${\mathcal O}(|{\mathcal Q}| \cdot |{\Sigma_r^n}| \cdot n )$
and
${\mathcal O}(|{\mathcal Q}^3| \cdot |{\Sigma_r^n}| \cdot {n^3} )$
respectively, where
n
is the number of components of the vectors represented by the NDD, and |
Q
| and Σ
$_{r}^{n}$
are the number of states and the alphabet of the NDD. On a prototype implementation, the computations of affine hulls of NDDs with more than 100000 states are done in seconds.