RISC JKU
fwf

GALA: Generalization ALgorithms and Applications


Supported by the Austrian Science Fund (FWF), Project P 28789-N32 (2016-2020)


Short Description

Generalization is a process of obtaining more general objects from concrete ones. It is a key concept in inductive reasoning. In its simplest form, generalization of two terms s and t is a term r such that s and t can be obtained from r by some variable substitutions. From all such generalizations, the interesting ones are those that can not be made more specific: least general generalizations.

The process of computing least general generalizations is known as anti-unification. It is a procedure dual to unification, which can be seen as a computation of most general common instances of the given terms (most general specifications).

Current research on anti-unification is dominated by practically oriented topics, which is not surprising, because generalization computation, in various forms, is an important ingredient of many applications in reasoning, learning, information extraction, data compression, software development and analysis, etc.

In this project we address challenges to generalization computation posed by new application domains. Some require studying generalization problems in a completely new theory. Some others may be dealt more adequately by improving existing algorithms. It is well-known that in many applications, the standard first-order anti-unification is too weak. We are concerned with the development of generalization algorithms for equational and higher-order theories (also with respect to special similarity relations and for terms in specific forms), their analysis, investigation of efficient special cases, free open source implementation, and applications.

Team

Software

Software developed in this project is incorporated into the library of unification and anti-unification algorithms.

Publications of Group Members

  1. T. Kutsia, C. Pau. Matching and Generalization Modulo Proximity and Tolerance Relations. In: A. Özgün and Y. Zinova, editors. Proceedings of TbiLLC 2019 - 13th International Tbilisi Symposium on Logic, Language, and Computation.Volume 13206 of Lecture Notes in Computer Science. Springer, 2022. 323–342. DOI: 10.1007/978-3-030-98479-3_16.
    PDF, BibTeX.
  2. B. Dundua, T. Kutsia, M. Rukhaia. Unranked Nominal Unification. In: A. Özgün and Y. Zinova, editors. Proceedings of TbiLLC 2019 - 13th International Tbilisi Symposium on Logic, Language, and Computation.Volume 13206 of Lecture Notes in Computer Science. Springer, 2022. 279–296. DOI: 10.1007/978-3-030-98479-3_14.
    PDF, BibTeX.
  3. C. Pau, T. Kutsia. Proximity-Based Unification and Matching for Fully Fuzzy Signatures. Proceedings of 30th IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2021. IEEE 2021. DOI: 10.1109/FUZZ45933.2021.9494438.
    PDF, BibTeX.
  4. M. Schmidt-Schauß, T. Kutsia, J. Levy, M. Villaret, Y. Kutz. Nominal Unification and Matching of Higher Order Expressions with Recursive Let. Fundamenta Informaticae, 185(3), 247–283, 2022. DOI: 10.3233/FI-222110.
    PDF, BibTeX.
  5. B. Dundua, T. Kutsia, M. Marin. Variadic equational matching in associative and commutative theories. Journal of Symbolic Computation. 106, 78–109, 2021. DOI: 10.1016/j.jsc.2021.01.001.
    PDF, BibTeX.
  6. D. Cerna, T. Kutsia. Higher-Order Pattern Generalization Modulo Equational Theories. Mathematical Structures in Computer Science, 30(6): 627–663, 2020. DOI: 10.1017/S0960129520000110.
    PDF, BibTeX.
  7. D. Cerna, T. Kutsia. Unital Anti-unification: Type and Algorithms. In: Z. M. Ariola, editor. Proceedings of the 5th International Conference on Formal Structures for Computation and Deduction, FSCD 2020. Volume 167 of Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl, 2020. 27:1–27:20. DOI: 10.4230/LIPIcs.FSCD.2020.26.
    PDF, BibTeX.
  8. B. Dundua, T. Kutsia, M. Marin, C. Pau. Constraint solving over multiple similarity relations. In: Z. M. Ariola, editor. Proceedings of the 5th International Conference on Formal Structures for Computation and Deduction, FSCD 2020. Volume 167 of Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl, 2020. 31:1–31:18. DOI: 10.4230/LIPIcs.FSCD.2020.30.
    PDF. BibTeX.
  9. D. Cerna, T. Kutsia. Idempotent Anti-unification. ACM Transactions on Computational Logic (TOCL) 21(2), 10:1–10:32. 2020. DOI: 10.1145/3359060.
    PDF, BibTeX.
  10. T. Kutsia, C. Pau. Proximity-Based Unification with Arity Mismatch. T. Kutsia and A. M. Marshall, eds. 34th International Workshop on Unification, UNIF 2020, technical Report 20-10 in RISC Report Series, RISC, Johannes Kepler University Linz, 9:1–9:6.
    PDF.
  11. I. Kotsireas, T. Kutsia, D. Simos. Constructing orthogonal designs in powers of two via symbolic computation and rewriting techniques. Annals of Mathematics and Artificial Intelligence. 88(1), 213–236, 2020. DOI: 10.1007/s10472-018-9607-9.
    PDF, BibTeX.
  12. M. Marin, B. Dundua, T. Kutsia. A Rule-Based System for Computation and Deduction in Mathematica. In: S. Escobar and N. Marti-Oliet, editors. Prpceedings of WRLA 2020 - Rewriting Logic and Its Applications. Volume 12328 of Lecture Notes in Computer Science. Springer, 2020. 57–74.
    PDF, BibTeX.
  13. B. Dundua, T. Kutsia, M. Marin, C. Pau. Extending the ρLog Calculus with Proximity Relations. In: G. Jaiani and D. Natroshvili, editors. Applications of Mathematics and Informatics in Natural Sciences and Engineering, AMINSE 2019. Volume 334 of Springer Proceedings in Mathematics & Statistics. Springer, Cham. 2020. 83–100.
    PDF, BibTeX.
  14. B. Dundua, T. Kutsia, M. Marin, M. Rukhaia. Specification and Analysis of ABAC Policies in a Rule-Based Framework. In: G. Jaiani and D. Natroshvili, editors. Applications of Mathematics and Informatics in Natural Sciences and Engineering, AMINSE 2019. Volume 334 of Springer Proceedings in Mathematics & Statistics. Springer, Cham. 2020. 101–116.
    PDF, BibTeX.
  15. T. Kutsia, C. Pau. Solving Proximity Constraints. In: M. Gabbrielli, editor. Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019. Revised Selected Papers. October 8–10, 2019, Porto, Portugal. Vol. 12042 of Lecture Notes in Computer Science. Springer, 2019. 107–122.
    PDF, BibTeX.
  16. B. Dundua, T. Kutsia, M. Marin. Variadic Equational Matching. In: C. Kaliszyk, E. Brady, A. Kohlhase, C. Sacerdoti Coen, editors. Intelligent Computer Mathematics - 12th International Conference, CICM 2019. July 9–12, 2019, Prague, Czech Republic. Vol. 11617 of Lecture Notes in Computer Science. Springer, 2019, 77–92.
    PDF, BibTeX.
  17. D. Cerna, T. Kutsia. A Generic Framework for Higher-Order Generalizations. In: H. Geuvers, editor. Proceedings of the 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019). June 25–29, 2019, Dortmund, Germany. Vol. 131 of the Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl, 2019, 10:1–10:19.
    PDF, BibTeX.
  18. M. Marin, T. Kutsia, B. Dundua. A Rule-based Approach to the Decidability of Safety of ABACα. In: F. Kerschbaum, A. Mashatan, J. Niu, A. J. Lee, editors. Proceedings of the 24th ACM Symposium on Access Control Models and Technologies, SACMAT 2019. June 3–6, 2019, Toronto, Canada. ACM, 2019, 173–178.
    PDF, BibTeX.
  19. T. Kutsia, C. Pau. Solving Proximity Constraints. S. Erbatur, D. Nantes, eds. 33nd International Workshop on Unification, UNIF 2019, 7 pages.
    PDF.
  20. A. Baumgartner, T. Kutsia. J. Levy, M. Villaret. Term-Graph Anti-Unification. In: H. Kirchner, editor. Proceedings of the 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018). July 9–12, 2018, Oxford, UK. Volume 108 of the Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl, 2018, 9:1–9:16.
    PDF, BibTeX.
  21. D. Cerna, T. Kutsia. Higher-Order Equational Pattern Anti-Unification. In: H. Kirchner, editor. Proceedings of the 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018). July 9–12, 2018, Oxford, UK. Volume 108 of the Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl, 2018, 11:1–11:16.
    PDF, BibTeX.
  22. T. Kutsia, C. Pau. Proximity-Based Generalization. In: M. Ayala-Rincon and Ph. Balbiani, editors. Proceedings of the 32nd International Workshop on Unification (UNIF 2018). July 7, 2018, Oxford, UK.
    PDF.
  23. D. Cerna, T. Kutsia. Towards Generalization Methods for Purely Idempotent Equational Theories. In: M. Ayala-Rincon and Ph. Balbiani, editors. Proceedings of the 32nd International Workshop on Unification (UNIF 2018). July 7, 2018, Oxford, UK.
  24. N. Amiridze, T. Kutsia. Anti-Unification and Natural Language Processing. In: A. Asudeh, V. de Paiva, and L. Moss, editors. Proceedings of the Fifth Workshop on Natural Language and Computer Science (NLCS 2018). July 7, 2018, Oxford, UK. EasyChair preprint 203, 2018. 12 pages.
    DOI. BibTeX.
  25. S. Alves, B. Dundua, M. Florido, T. Kutsia. Pattern-based calculi with finitary matching. Logic Journal of the IGPL. 26(2):203–243.
    PDF from the publisher's page, BibTeX.
  26. J. Blömer, I. S Kotsireas, T. Kutsia, D. Simos (editors). Mathematical Aspects of Computer and Information Sciences. 7th International Conference, MACIS 2017, Vienna, Austria, November 15-17, 2017, Proceedings. Lecture Notes in Computer Science 10693, Springer, 2017.
    Web page, BibTeX.
  27. D. Cerna, M. P Lettmann. Integrating a Global Induction Mechanism into a Sequent Calculus. In: R. A. Schmidt, C. Nalon, editors. Automated Reasoning with Analytic Tableaux and Related Methods - 26th International Conference, TABLEAUX 2017, Brasília, Brazil, September 25-28, 2017, Proceedings. Lecture Notes in Computer Science 10501, Springer, 2017, 278-294.
    PDF, BibTeX.
  28. B. Dundua, T. Kutsia, K. Reisenberger-Hagmayr. An overview of PρLog. In: Y. Lierler and W. Taha, editors. Proceedings of the 19th International Symposium on Practical Aspects of Declarative Languages, PADL 2017. Volume 10137 of of Lecture Notes in Computer Science. Springer, 2017. 34–49.
    PDF, BibTeX.
  29. B. Dundua, T. Kutsia, K. Reisenberger-Hagmayr. PρLog: Combining Logic Programming with Conditional Transformation Systems (Tool Description). In: M. Carro, A. King, N. Saeedloei, and M. De Vos, editors. Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016. Vol. 52 of OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl, 2016, 10.1–10.5.
    PDF, BibTeX.
  30. B. Konev, T. Kutsia. Anti-Unification of Concepts in Description Logic EL. In: Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning, KR 2016. April 25–29, 2016, Cape Town, South Africa. The AAAI Press, 2016. 227–236.
    PDF, BibTeX.

Technical Reports

PhD Thesis

Contact

Temur Kutsia (Project leader)
Research Institute for Symbolic Computation
Johannes Kepler University Linz
Altenbergerstrasse 69
A-4040 Linz, Austria
Phone: +43 (0)732 2468 9982
kutsia@risc.jku.at