Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Computing the Transitive Closure of a Union of Affine Integer Tuple Relations
verfasst von : Anna Beletska, Denis Barthou, Wlodzimierz Bielecki, Albert Cohen
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper proposes a method to compute the transitive closure of a union of affine relations on integer tuples. Within Presburger arithmetics, complete algorithms to compute the transitive closure exist for convex polyhedra only. In presence of non-convex relations, there exist little but special cases and incomplete heuristics. We introduce a novel sufficient and necessary condition defining a class of relations for which an exact computation is possible. Our method is immediately applicable to a wide area of symbolic computation problems. It is illustrated on representative examples and compared with state-of-the-art approaches.