Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02026-1_9 | COCOA |
Keywords | Field | DocType |
transitive closure,integer tuples,affine integer tuple relations,affine relation,exact computation,complete algorithm,necessary condition,convex polyhedron,presburger arithmetics,incomplete heuristics,symbolic computation problem,symbolic computation,presburger arithmetic | Affine transformation,Integer,Discrete mathematics,Combinatorics,Tuple,Computer science,Polyhedron,Symbolic computation,Heuristics,Transitive closure,Transitive relation | Conference |
Volume | ISSN | Citations |
5573 | 0302-9743 | 13 |
PageRank | References | Authors |
0.82 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anna Beletska | 1 | 68 | 4.99 |
| Denis Barthou | 2 | 238 | 26.14 |
| Wlodzimierz Bielecki | 3 | 107 | 17.46 |
| Albert Cohen | 4 | 1002 | 72.30 |