Document Open Access Logo

Higher-Order Equational Pattern Anti-Unification

Authors David M. Cerna, Temur Kutsia

PDF
Thumbnail PDF

File

LIPIcs.FSCD.2018.12.pdf
  • Filesize: 492 kB
  • 17 pages

Document Identifiers

Author Details

David M. Cerna
  • Research Institute for Symbolic Computation, Johannes Kepler University, Linz, Austria
Temur Kutsia
  • Research Institute for Symbolic Computation, Johannes Kepler University, Linz, Austria

Funding

This research is supported by the FWF project P28789-N32.

Cite As Get BibTex

David M. Cerna and Temur Kutsia. Higher-Order Equational Pattern Anti-Unification. In 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 108, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSCD.2018.12

Abstract

We consider anti-unification for simply typed lambda terms in associative, commutative, and associative-commutative theories and develop a sound and complete algorithm which takes two lambda terms and computes their generalizations in the form of higher-order patterns. The problem is finitary: the minimal complete set of generalizations contains finitely many elements. We define the notion of optimal solution and investigate special fragments of the problem for which the optimal solution can be computed in linear or polynomial time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Rewrite systems
  • Theory of computation → Higher order logic
Keywords
  • Simply typed lambda calculus
  • anti-unification
  • equational theories

Metrics

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

References

  1. 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.
  2. Henk Barendregt. The Lambda Calculus. Its Syntax and Semantics. North Holland, 1984. Google Scholar
  3. 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.
  4. Alexander Baumgartner. Anti-Unification Algorithms: Design, Analysis, and Implementation. PhD thesis, Johannes Kepler University Linz, 2015. Google Scholar
  5. Alexander Baumgartner and Temur Kutsia. A library of anti-unification algorithms. In Eduardo Fermé and João Leite, editors, Logics in Artificial Intelligence - 14th European Conference, JELIA 2014. Proceedings, volume 8761 of Lecture Notes in Computer Science, pages 543-557. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11558-0_38.
  6. 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.
  7. Alexander Baumgartner, Temur Kutsia, Jordi Levy, and Mateu Villaret. A variant of higher-order anti-unification. In Femke van Raamsdonk, editor, 24th International Conference on Rewriting Techniques and Applications, RTA 2013, volume 21 of LIPIcs, pages 113-127. Schloss Dagstuhl, 2013. Google Scholar
  8. 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. Google Scholar
  9. Tarek R. Besold, Kai-Uwe Kühnberger, and Enric Plaza. Towards a computational- and algorithmic-level account of concept blending using analogies and amalgams. Connect. Sci., 29(4):387-413, 2017. URL: http://dx.doi.org/10.1080/09540091.2017.1326463.
  10. Gilles Dowek. Higher-order unification and matching. In John Alan Robinson and Andrei Voronkov, editors, Handbook of Automated Reasoning, pages 1009-1062. Elsevier and MIT Press, 2001. Google Scholar
  11. Temur Kutsia, Jordi Levy, and Mateu Villaret. Anti-unification for unranked terms and hedges. J. Autom. Reasoning, 52(2):155-190, 2014. URL: http://dx.doi.org/10.1007/s10817-013-9285-6.
  12. Tomer Libal and Alexander Steen. Towards a substitution tree based index for higher-order resolution theorem provers. In Pascal Fontaine, Stephan Schulz, and Josef Urban, editors, Proceedings of the 5th PAAR Workshop, volume 1635 of CEUR Workshop Proceedings, pages 82-94. CEUR-WS.org, 2016. URL: http://ceur-ws.org/Vol-1635/paper-08.pdf.
  13. Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. J. Log. Comput., 1(4):497-536, 1991. URL: http://dx.doi.org/10.1093/logcom/1.4.497.
  14. Frank Pfenning. Unification and anti-unification in the calculus of constructions. In LICS, pages 74-85. IEEE Computer Society, 1991. Google Scholar
  15. Brigitte Pientka. Higher-order term indexing using substitution trees. ACM TOCL, 11(1), 2009. URL: http://dx.doi.org/10.1145/1614431.1614437.
  16. Ute Schmid. Inductive Synthesis of Functional Programs, Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning, volume 2654 of Lecture Notes in Computer Science. Springer, 2003. Google Scholar
  17. Martin Schmidt, Ulf Krumnack, Helmar Gust, and Kai-Uwe Kühnberger. Heuristic-driven theory projection: An overview. In Henri Prade and Gilles Richard, editors, Computational Approaches to Analogical Reasoning: Current Trends, volume 548 of Studies in Computational Intelligence, pages 163-194. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-642-54516-0_7.
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 About DROPS Imprint Privacy Contact