Document Open Access Logo

Term-Graph Anti-Unification

Authors Alexander Baumgartner, Temur Kutsia, Jordi Levy, Mateu Villaret

PDF
Thumbnail PDF

File

LIPIcs.FSCD.2018.9.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Alexander Baumgartner
  • Department of Computer Science (DCC), University of Chile, Santiago, Chile
Temur Kutsia
  • Research Institute for Symbolic Computation, Johannes Kepler University Linz, Austria
Jordi Levy
  • Artificial Intelligence Research Institute (IIIA), Spanish National Research Council, (CSIC), Barcelona, Spain
Mateu Villaret
  • Departament d'Informàtica, Matemàtica Aplicada i Estadística, Universitat de Girona, Girona, Spain

Funding

Supported by the Austrian Science Fund (FWF) under the projects P 28789-N32 and J 3909-N31, by MINECO/FEDER projects TIN2015-71799-C2-1-P (RASO) and TIN2015-66293-R (LoCos), and by UdG project MPCUdG2016/055.

Cite AsGet BibTex

Alexander Baumgartner, Temur Kutsia, Jordi Levy, and Mateu Villaret. Term-Graph Anti-Unification. In 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 108, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSCD.2018.9

Abstract

We study anti-unification for possibly cyclic, unranked term-graphs and develop an algorithm, which computes a minimal complete set of generalizations for them. For bisimilar graphs the algorithm computes the join in the lattice generated by a functional bisimulation. These results generalize anti-unification for ranked and unranked terms to the corresponding term-graphs, and solve also anti-unification problems for rational terms and dags. Our results open a way to widen anti-unification based code clone detection techniques from a tree representation to a graph representation of the code.

Subject Classification

ACM Subject Classification
  • Theory of computation → Equational logic and rewriting
Keywords
  • Cyclic term-graps
  • anti-unification
  • least general generalization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hassan Aït-Kaci and Gabriella Pasi. Lattice operations on terms over similar signatures. In Pre-proceedings of the 27th International Symposium on Logic-based Program Synthesis and Transformation (LOPSTR'17), 2017. URL: https://arxiv.org/abs/1709.00964.
  2. María Alpuente, Santiago Escobar, Javier Espert, and José Meseguer. ACUOS: A system for modular ACU generalization with subtyping and inheritance. In Fermé and Leite [17], pages 573-581. URL: http://dx.doi.org/10.1007/978-3-319-11558-0.
  3. María Alpuente, Santiago Escobar, Javier Espert, and José Meseguer. A modular order-sorted equational generalization algorithm. Inf. Comput., 235:98-136, 2014. URL: http://dx.doi.org/10.1016/j.ic.2014.01.006.
  4. Zena M. Ariola and Jan Willem Klop. Equational term graph rewriting. Fundam. Inform., 26(3/4):207-240, 1996. Google Scholar
  5. Zena M. Ariola and Jan Willem Klop. Lambda calculus with explicit recursion. Inf. Comput., 139(2):154-233, 1997. URL: http://dx.doi.org/10.1006/inco.1997.2651.
  6. Hendrik Pieter Barendregt, Marko C. J. D. van Eekelen, John R. W. Glauert, Richard Kennaway, Marinus J. Plasmeijer, and M. Ronan Sleep. Term graph rewriting. In J. W. de Bakker, A. J. Nijman, and Philip C. Treleaven, editors, PARLE, Parallel Architectures and Languages Europe, Volume II: Parallel Languages, volume 259 of LNCS, pages 141-158. Springer, 1987. URL: http://dx.doi.org/10.1007/3-540-17945-3.
  7. Adam D. Barwell, Christopher Brown, and Kevin Hammond. Finding parallel functional pearls: Automatic parallel recursion scheme detection in Haskell functions via anti-unification. Future Generation Comp. Syst., 79:669-686, 2018. URL: http://dx.doi.org/10.1016/j.future.2017.07.024.
  8. Alexander Baumgartner. Anti-Unification Algorithms: Design, Analysis, and Implementation. PhD thesis, Johannes Kepler University Linz, 2015. Available from URL: http://www.risc.jku.at/publications/download/risc_5180/phd-thesis.pdf.
  9. Alexander Baumgartner and Temur Kutsia. A library of anti-unification algorithms. In Fermé and Leite [17], pages 543-557. URL: http://dx.doi.org/10.1007/978-3-319-11558-0.
  10. Alexander Baumgartner and Temur Kutsia. Unranked second-order anti-unification. Inf. Comput., 255:262-286, 2017. URL: http://dx.doi.org/10.1016/j.ic.2017.01.005.
  11. Alexander Baumgartner, Temur Kutsia, Jordi Levy, and Mateu Villaret. Higher-order pattern anti-unification in linear time. J. Autom. Reasoning, 58(2):293-310, 2017. URL: http://dx.doi.org/10.1007/s10817-016-9383-3.
  12. Alexander Baumgartner, Temur Kutsia, Jordi Levy, and Mateu Villaret. Term-graph anti-unification. RISC Report Series 18-02, Research Institute for Symbolic Computation, Johannes Kepler University Linz, Austria, 2018. Google Scholar
  13. Tarek Richard Besold and Enric Plaza. Generalize and blend: Concept blending based on generalization, analogy, and amalgams. In Hannu Toivonen, Simon Colton, Michael Cook, and Dan Ventura, editors, Proceedings of the Sixth International Conference on Computational Creativity, pages 150-157. computationalcreativity.net, 2015. URL: http://computationalcreativity.net/iccc2015/?page_id=331.
  14. Petr Bulychev and Marius Minea. An evaluation of duplicate code detection using anti-unification. In Proc. 3rd International Workshop on Software Clones, 2009. Google Scholar
  15. Andrea Corradini and Fabio Gadducci. An algebraic presentation of term graphs, via gs-monoidal categories. Applied Categorical Structures, 7(4):299-331, 1999. URL: http://dx.doi.org/10.1023/A:1008647417502.
  16. Rylan Cottrell, Joseph J. C. Chang, Robert J. Walker, and Jörg Denzinger. Determining detailed structural correspondence for generalization tasks. In Ivica Crnkovic and Antonia Bertolino, editors, 6th joint meeting of the European Software Engineering Conference and the ACM SIGSOFT Int. Symposium on Foundations of Software Engineering, pages 165-174. ACM, 2007. Google Scholar
  17. Eduardo Fermé and João Leite, editors. Logics in Artificial Intelligence - 14th European Conference, JELIA 2014, Funchal, Madeira, Portugal, September 24-26, 2014. Proceedings, volume 8761 of Lecture Notes in Computer Science. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11558-0.
  18. Adelaine Gelain, Cristiano D. Vasconcellos, Carlos Camarão, and Rodrigo Ribeiro. Type inference for GADTs and anti-unification. In Alberto Pardo and S. Doaitse Swierstra, editors, Programming Languages - 19th Brazilian Symposium SBLP 2015, volume 9325 of LNCS, pages 16-30. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-24012-1.
  19. Richard Kennaway, Jan Willem Klop, M. Ronan Sleep, and Fer-Jan de Vries. On the adequacy of graph rewriting for simulating term rewriting. ACM Trans. Program. Lang. Syst., 16(3):493-523, 1994. URL: http://dx.doi.org/10.1145/177492.177577.
  20. Jan Willem Klop. Term graph rewriting. In Gilles Dowek, Jan Heering, Karl Meinke, and Bernhard Möller, editors, Higher-Order Algebra, Logic, and Term Rewriting, Second International Workshop, HOA'95, Selected Papers, volume 1074 of LNCS, pages 1-16. Springer, 1995. URL: http://dx.doi.org/10.1007/3-540-61254-8.
  21. Boris Konev and Temur Kutsia. Anti-unification of concepts in description logic EL. In Chitta Baral, James P. Delgrande, and Frank Wolter, editors, Principles of Knowledge Representation and Reasoning: Fifteenth International Conference, KR'16, pages 227-236. AAAI Press, 2016. URL: http://www.aaai.org/Library/KR/kr16contents.php.
  22. Temur Kutsia, Jordi Levy, and Mateu Villaret. Anti-unification for unranked terms and hedges. J. Autom. Reasoning, 52(2):155-190, 2014. Google Scholar
  23. Giorgio Levi. A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo, 9(4):341, 1973. Google Scholar
  24. James J McGregor. Backtrack search algorithms and the maximal common subgraph problem. Software: Practice and Experience, 12(1):23-34, 1982. Google Scholar
  25. Santiago Ontañón and Ali Shokoufandeh. Refinement-based similarity measures for directed labeled graphs. In Ashok K. Goel, M. Belén Díaz-Agudo, and Thomas Roth-Berghofer, editors, Case-Based Reasoning Research and Development - 24th International Conference, ICCBR'16, volume 9969 of LNCS, pages 311-326. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-47096-2.
  26. Gordon D. Plotkin. A note on inductive generalization. Machine Intell., 5(1):153-163, 1970. Google Scholar
  27. Detlef Plump. Term graph rewriting. In H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg, editors, Handbook of Graph Grammars and Computing by Graph Transformation, volume 2, chapter 1, pages 3-61. World Scientific, 1999. Google Scholar
  28. Simon J. Thompson, Huiqing Li, and Andreas Schumacher. The pragmatics of clone detection and elimination. Programming Journal, 1(2):8, 2017. URL: http://dx.doi.org/10.22152/programming-journal.org/2017/1/8.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact