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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alias, C., Barthou, D.: On domain specific languages re-engineering. In: Glück, R., Lowry, M. (eds.) GPCE 2005. LNCS, vol. 3676, pp. 63–77. Springer, Heidelberg (2005)
Barthou, D., Feautrier, P., Redon, X.: On the equivalence of two systems of affine recurrence equations. In: Monien, B., Feldmann, R.L. (eds.) Euro-Par 2002. LNCS, vol. 2400, pp. 309–313. Springer, Heidelberg (2002)
Beletska, A., Bielecki, W., San Pietro, P.: Extracting coarse-grained parallelism in program loops with the slicing framework. In: ISPDC 2007: Proceedings of the Sixth International Symposium on Parallel and Distributed Computing, p. 29. IEEE Computer Society Press, Washington (2007)
Bielecki, W., Klimek, T., Trifunovic, K.: Calculating exact transitive closure for a normalized affine integer tuple relation. Journal of Electronic Notes in Discrete Mathematics 33, 7–14 (2009)
Boigelot, B.: Symbolic Methods for Exploring Infinite State Spaces. PhD thesis, Université de Liège (1998)
Boigelot, B., Wolper, P.: Symbolic verification with periodic sets. In: Dill, D.L. (ed.) CAV 1994. LNCS, vol. 818, pp. 55–67. Springer, Heidelberg (1994)
Comon, H., Jurski, Y.: Multiple counters automata, safety analysis and presburger arithmetic. In: Vardi, M.Y. (ed.) CAV 1998. LNCS, vol. 1427, pp. 268–279. Springer, Heidelberg (1998)
Darte, A., Robert, Y., Vivien, F.: Scheduling and Automatic Parallelization. Birkhaüser (2000)
Kelly, W., Pugh, W., Rosser, E., Shpeisman, T.: Transitive closure of infinite graphs and its applications. Int. J. Parallel Programming 24(6), 579–598 (1996)
Shashidhar, K.C., Bruynooghe, M., Catthoor, F., Janssens, G.: An automatic verification technique for loop and data reuse transformations based on geometric modeling of programs. Journal of Universal Computer Science 9(3), 248–269 (2003)
The Omega project, http://www.cs.umd.edu/projects/omega
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beletska, A., Barthou, D., Bielecki, W., Cohen, A. (2009). Computing the Transitive Closure of a Union of Affine Integer Tuple Relations. In: Du, DZ., Hu, X., Pardalos, P.M. (eds) Combinatorial Optimization and Applications. COCOA 2009. Lecture Notes in Computer Science, vol 5573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02026-1_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-02026-1_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02025-4
Online ISBN: 978-3-642-02026-1
eBook Packages: Computer ScienceComputer Science (R0)