Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-22T04:07:55.320Z Has data issue: false hasContentIssue false
  • English
  • Français

Analysing graph transformation systems through constraint handling rules

Published online by Cambridge University Press:  20 July 2010

FRANK RAISER  and
THOM FRÜHWIRTH
FRANK RAISER
Affiliation:
Faculty of Engineering and Computer Sciences, Ulm University, Germany (e-mail: [email protected], [email protected])
THOM FRÜHWIRTH
Affiliation:
Faculty of Engineering and Computer Sciences, Ulm University, Germany (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Graph transformation systems (GTS) and constraint handling rules (CHR) are non-deterministic rule-based state transition systems. CHR is well known for its powerful confluence and program equivalence analyses, for which we provide the basis in this work to apply them to GTS. We give a sound and complete embedding of GTS in CHR, investigate confluence of an embedded GTS and provide a program equivalence analysis for GTS via the embedding. The results confirm the suitability of CHR-based program analyses for other formalisms embedded in CHR.

Keywords

Graph transformation systemsConstraint handling rulesProgram analysis
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Issue 1 , January 2011 , pp. 65 - 109
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abdennadher, S. and Frühwirth, T. 1999. Operational equivalence of CHR programs and constraints. In Principles and Practice of Constraint Programming, CP 1999, Jaffar, J., Ed. Lecture Notes in Computer Science, vol. 1713. Springer-Verlag, 43–57.Google Scholar
Abdennadher, S. and Frühwirth, T. 2003. Integration and optimization of rule-based constraint solvers. In Logic Based Program Synthesis and Transformation, 13th International Symposium LOPSTR 2003, Uppsala, Sweden, August 25–27, 2003, Revised Selected Papers, Bruynooghe, M., Ed. Lecture Notes in Computer Science, vol. 3018. Springer-Verlag, 198–213.Google Scholar
Abdennadher, S., Frühwirth, T. and Meuss, H. 1999. Confluence and semantics of constraint simplification rules. Constraints 4, 2, 133–165.CrossRefGoogle Scholar
Abdennadher, S. and Marte, M. 2000. University course timetabling using Constraint Handling Rules. In Special Issue on Constraint Handling Rules, Holzbaur, C. and Frühwirth, T., Eds. Journal of Applied Artificial Intelligence, vol. 14(4). Taylor & Francis, 311–325.Google Scholar
Abdennadher, S. and Sobhi, I. 2007. Generation of rule-based constraint solvers: Combined approach. In Logic-Based Program Synthesis and Transformation, 17th International Symposium, LOPSTR 2007, Kongens Lyngby, Denmark, August 23-24, 2007, Revised Selected Papers, King, A., Ed. Lecture Notes in Computer Science, vol. 4915. Springer-Verlag, 106–120.Google Scholar
Baader, F. and Nipkow, T. 1998. Term Rewriting and All That. Cambridge University Press, New York.CrossRefGoogle Scholar
Bakewell, A., Plump, D. and Runciman, C. 2003. Specifying pointer structures by graph reduction. In Applications of Graph Transformations with Industrial Relevance, Second International Workshop, AGTIVE 2003, Revised Selected and Invited Papers, Pfaltz, J. L., Nagl, M. and Böhlen, B., Eds. Lecture Notes in Computer Science, vol. 3062. Springer-Verlag, Charlottesville, VA, 30–44.Google Scholar
Barranco-Mendoza, A. 2005. Stochastic and Heuristic Modelling for Analysis of the Growth of Pre-Invasive Lesions and for a Multidisciplinary Approach to Early Cancer Diagnosis. PhD thesis, Simon Fraser University, Burnaby, Canada.Google Scholar
Bavarian, M. and Dahl, V. 2006. Constraint based methods for biological sequence analysis. Journal of Universal Computer Science 12, 11, 1500–1520.Google Scholar
Betz, H. 2007. Relating coloured Petri nets to Constraint Handling Rules. In CHR '07 (Porto, Portugal), Djelloul, K., Duck, G. J. and Sulzmann, M., Eds. 33–47.Google Scholar
Betz, H. and Frühwirth, T. 2005. A Linear-Logic Semantics for Constraint Handling Rules. In Principles and Practice of Constraint Programming, 11th International Conference, CP 2005, van Beek, P., Ed. Lecture Notes in Computer Science, vol. 3709. Springer-Verlag, Sitges, Spain, 137–151.CrossRefGoogle Scholar
Blostein, D., Fahmy, H., and Grbavec, A. 1995. Practical use of graph rewriting. In Fifth Workshop on Graph Grammars and Their Application To Computer Science, Cuny, J. E., Ehrig, H., Engels, G. and Rozenberg, G., Eds. Lecture Notes in Computer Science, vol. 1073. Springer-Verlag, 38–55.Google Scholar
Dahl, V. and Maharshak, E. 2009. DNA replication as a model for computational linguistics. In IWINAC '09: Proceedings of the Third International Work-Conference on the Interplay Between Natural and Artificial Computation, Mira, J. M., Ferrández, J. M., Álvarez, J. R., de la Paz, F. and Toledo, F. J., Eds. Lecture Notes in Computer Science, vol. 5601. Springer-Verlag, 346–355.Google Scholar
Duck, G. J., Stuckey, P. J., and Brand, S. 2006. ACD term rewriting. In ICLP '06 (Seattle, Washington), Etalle, S. and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 4079. Springer-Verlag, 117–131.Google Scholar
Duck, G. J., Stuckey, P. J., and Sulzmann, M. 2007. Observable confluence for constraint handling rules. In Logic Programming, 23rd International Conference, ICLP 2007, Dahl, V. and Niemelä, I., Eds. Lecture Notes in Computer Science, vol. 4670. Springer-Verlag, Porto, Portugal, 224–239.Google Scholar
Ehrig, H., Ehrig, K., Prange, U. and Taentzer, G. 2006. Fundamentals of Algebraic Graph Transformation. Springer-Verlag.Google Scholar
Ehrig, H. and König, B. 2004. Deriving bisimulation congruences in the DPO approach to graph rewriting. In Foundations of Software Science and Computation Structures, 7th International Conference, FOSSACS 2004, Walukiewicz, I., Ed. Lecture Notes in Computer Science, vol. 2987. Springer-Verlag, Barcelona, Spain, 151–166.Google Scholar
Frühwirth, T. 2000. Proving termination of constraint solver programs. In Selected Papers from the Joint ERCIM/Compulog Net Workshop on New Trends in Constraints, Apt, K. R., Kakas, A. C., Monfroy, E. and Rossi, F., Eds. Lecture Notes in Computer Science, vol. 1865. Springer-Verlag, 298–317.Google Scholar
Frühwirth, T. 2005. Parallelizing union-find in constraint handling rules using confluence analysis. In Logic Programming, 21st International Conference, ICLP 2005, Gabbrielli, M. and Gupta, G., Eds. Lecture Notes in Computer Science, vol. 3668. Springer-Verlag, 113–127.Google Scholar
Frühwirth, T. 2009. Constraint Handling Rules. Cambridge University Press.CrossRefGoogle Scholar
Huet, G. 1980. Confluent reductions: Abstract properties and applications to term rewriting systems: Abstract properties and applications to term rewriting systems. Journal of the ACM 27, 4, 797–821.CrossRefGoogle Scholar
Kreowski, H.-J. and Valiente, G. 2000. Redundancy and subsumption in high-level replacement systems. In TAGT'98: Selected papers from the 6th International Workshop on Theory and Application of Graph Transformations, Ehrig, H. G., Engels, G., Kreowski, H.-J. and Rozenberg, G., Eds. Lecture Notes in Computer Science, vol. 1765. Springer-Verlag, 215–227.CrossRefGoogle Scholar
Lam, E. S. and Sulzmann, M. 2006. Towards Agent Programming in CHR. In CHR '06: Proc. 3rd Workshop on Constraint Handling Rules, Schrijvers, T. and Frühwirth, T., Eds. K. U. Leuven, Tech. Rep. CW 452, 17–31.Google Scholar
Lam, E. S. and Sulzmann, M. 2008. Finally, a comparison between Constraint Handling Rules and join-calculus. In CHR '08 (Hagenberg, Austria), Schrijvers, T., Raiser, F., and Frühwirth, T., Eds. RISC Report Series 08-10, University of Linz, Austria, 51–66.Google Scholar
Löwe, M. 1993. Algebraic approach to single-pushout graph transformation. Theoretical Computer Science 109, 1&2, 181–224.CrossRefGoogle Scholar
Löwe, M. and Müller, J. 1993. Algebraische Graphersetzung: mathematische Modellierung und Konfluenz. Tech. Rep. 93-37, Technische Universität, Berlin.Google Scholar
Newman, M. 1942. On theories with a combinatorial definition of equivalence. Annals of Mathematics 43, 2, 223–242.CrossRefGoogle Scholar
Pilozzi, P. and De Schreye, D. 2008. Termination analysis of CHR revisited. In ICLP '08, de la Banda, M. García and Pontelli, E., Eds. Lecture Notes in Computer Science, vol. 5366. Springer-Verlag, 501–515.Google Scholar
Plump, D. 1995. On Termination of graph rewriting. In Graph-Theoretic Concepts in Computer Science, 21st International Workshop, WG '95, Proceedings, Nagl, M., Ed. Lecture Notes in Computer Science, vol. 1017. Aachen, Germany, 88–100.CrossRefGoogle Scholar
Plump, D. 2005. Confluence of graph transformation revisited. In Processes, Terms and Cycles, Middeldorp, A., van Oostrom, V., van Raamsdonk, F. and de Vrijer, R. C., Eds. Lecture Notes in Computer Science, vol. 3838. Springer-Verlag, 280–308.Google Scholar
Pretschner, A., Slotosch, O., Aiglstorfer, E. and Kriebel, S. 2004. Model-based testing for real. J. Software Tools for Technology Transfer (STTT) 5, 2–3, 140–157.CrossRefGoogle Scholar
Raiser, F. 2007. Graph Transformation Systems in CHR. In Logic Programming, 23rd International Conference, ICLP 2007, Dahl, V. and Niemelä, I., Eds. Lecture Notes in Computer Science, vol. 4670. Springer-Verlag, Porto, Portugal, 240–254.Google Scholar
Raiser, F. 2008. Semi-automatic generation of CHR solvers for global constraints. In Principles and Practice of Constraint Programming, 14th International Conference, CP 2008, Stuckey, P. J., Ed. Lecture Notes in Computer Science, vol. 5202. Springer-Verlag, Sydney, Australia, 588–592.Google Scholar
Raiser, F. 2009. Research summary: Analysing graph transformation systems using extended methods from constraint handling rules. In Twenty-fifth International Conference on Logic Programming, ICLP, Hill, P. M. and Warren, D. S., Eds. Lecture Notes in Computer Science, vol. 5649. Springer-Verlag, Pasadena, CA, 540–541.Google Scholar
Raiser, F., Betz, H. and Frühwirth, T. 2009. Equivalence of CHR states revisited. In Sixth International Workshop on Constraint Handling Rules (CHR), Raiser, F. and Sneyers, J., Eds. K. U. Leuven, Tech. Rep. CW 555, 34–48.Google Scholar
Raiser, F. and Frühwirth, T. 2009a. Operational equivalence of graph transformation systems. In Sixth International Workshop on Constraint Handling Rules (CHR), Raiser, F. and Sneyers, J., Eds. K. U. Leuven, Tech. Rep. CW 555, 49–62.Google Scholar
Raiser, F. and Frühwirth, T. 2009b. Strong joinability analysis for graph transformation systems in CHR. Electronic Notes in Theoretical Computer Science – Proceedings of the Fifth International Workshop on Computing with Terms and Graphs (TERMGRAPH 2009) 253, 4, 91–111.Google Scholar
Rangel, G., Lambers, L., König, B., Ehrig, H. and Baldan, P. 2008. Behavior preservation in model refactoring using DPO transformations with borrowed contexts. In Proceedings of ICGT '08 (International Conference on Graph Transformation). Lecture Notes in Computer Science, vol. 5214. Springer-Verlag, 242–256.Google Scholar
Sneyers, J., Van Weert, P., Schrijvers, T. and De Koninck, L. 2010. As time goes by: Constraint Handling Rules – A survey of CHR research between 1998 and 2007. Theory and Practice of Logic Programming 10, 1, 1–47.CrossRefGoogle Scholar
Sulzmann, M., Schrijvers, T., and Stuckey, P. J. 2006. Principal type inference for GHC-style multi-parameter type classes. In APLAS '06: Proceedings of the Fourth Asian Symposium on Programming Languages and Systems (Sydney, Australia), Kobayashi, N., Ed. Lecture Notes in Computer Science, vol. 4279. Springer-Verlag, 26–43.CrossRefGoogle Scholar
Van Weert, P. 2008. JCHR. URL: http://www.cs.kuleuven.be/~petervw/JCHR.Google Scholar
Van Weert, P., Sneyers, J. and Demoen, B. 2008. Aggregates for CHR through program transformation. In LOPSTR '07, Revised Selected Papers (Kongens Lyngby, Denmark), King, A., Ed. Lecture Notes in Computer Science, vol. 4915, 59–73.Google Scholar
Van Weert, P., Sneyers, J., Schrijvers, T. and Demoen, B. 2006. Extending CHR with negation as absence. In CHR '06 (Venice, Italy), Schrijvers, T. and Frühwirth, T., Eds. K. U. Leuven, Department of Computer Science, Tech. Rep. CW 452, 125–140.Google Scholar
Voets, D., Pilozzi, P. and De Schreye, D. 2008. A New Approach to Termination Analysis of CHR. Tech. Rep. CW 506, K. U. Leuven, Department of Computer Science, Leuven, Belgium.Google Scholar
Wasserthal, M. 2009. An Extensible Platform for the Analysis of Graph Transformation Systems using Constraint Handling Rules. Diploma thesis, Ulm University, Ulm, Germany.Google Scholar