# Generalization ALgorithms and Applications [GALA]

### Project Lead

### Project Duration

01/02/2016 - 31/01/2021### Project URL

Go to Website## Partners

### The Austrian Science Fund (FWF)

## Publications

### 2020

[Cerna]

### Unital Anti-Unification: Type and Algorithms

#### David M. Cerna , Temur Kutsia

In: 5th International Conference on Formal Structures for Computation and Deduction, {FSCD} 2020, June 29-July 6, 2020, Paris, France (Virtual Conference, Zena M. Ariola (ed.), Proceedings of FSCD, LIPICS 16720-02, pp. 1-20. 2020. 1868-8969. [url]@

author = {David M. Cerna and Temur Kutsia},

title = {{Unital Anti-Unification: Type and Algorithms}},

booktitle = {{5th International Conference on Formal Structures for Computation and Deduction, {FSCD} 2020, June 29-July 6, 2020, Paris, France (Virtual Conference}},

language = {english},

abstract = {Unital equational theories are defined by axioms that assert the existence of the unit element for some function symbols. We study anti-unification (AU) in unital theories and address the problems of establishing generalization type and designing anti-unification algorithms. First, we prove that when the term signature contains at least two unital functions, anti-unification is of the nullary type by showing that there exists an AU problem, which does not have a minimal complete set of generalizations. Next, we consider two special cases: the linear variant and the fragment with only one unital symbol, and design AU algorithms for them. The algorithms are terminating, sound, complete and return tree grammars from which set of generalizations can be constructed. Anti-unification for both special cases is finitary. Further, the algorithm for the one-unital fragment is extended to the unrestricted case. It terminates and returns a tree grammar which produces an infinite set of generalizations. At the end, we discuss how the nullary type of unital anti-unification might affect the anti-unification problem in some combined theories, and list some open questions. },

series = {LIPICS},

volume = {167},

number = {20-02},

pages = {1--20},

isbn_issn = {1868-8969},

year = {2020},

editor = {Zena M. Ariola},

refereed = {yes},

keywords = {Anti-unification, tree grammars, unital theories, collapse theories},

length = {19},

conferencename = {FSCD},

url = {https://doi.org/10.4230/LIPIcs.FSCD.2020.26}

}

**inproceedings**{RISC6237,author = {David M. Cerna and Temur Kutsia},

title = {{Unital Anti-Unification: Type and Algorithms}},

booktitle = {{5th International Conference on Formal Structures for Computation and Deduction, {FSCD} 2020, June 29-July 6, 2020, Paris, France (Virtual Conference}},

language = {english},

abstract = {Unital equational theories are defined by axioms that assert the existence of the unit element for some function symbols. We study anti-unification (AU) in unital theories and address the problems of establishing generalization type and designing anti-unification algorithms. First, we prove that when the term signature contains at least two unital functions, anti-unification is of the nullary type by showing that there exists an AU problem, which does not have a minimal complete set of generalizations. Next, we consider two special cases: the linear variant and the fragment with only one unital symbol, and design AU algorithms for them. The algorithms are terminating, sound, complete and return tree grammars from which set of generalizations can be constructed. Anti-unification for both special cases is finitary. Further, the algorithm for the one-unital fragment is extended to the unrestricted case. It terminates and returns a tree grammar which produces an infinite set of generalizations. At the end, we discuss how the nullary type of unital anti-unification might affect the anti-unification problem in some combined theories, and list some open questions. },

series = {LIPICS},

volume = {167},

number = {20-02},

pages = {1--20},

isbn_issn = {1868-8969},

year = {2020},

editor = {Zena M. Ariola},

refereed = {yes},

keywords = {Anti-unification, tree grammars, unital theories, collapse theories},

length = {19},

conferencename = {FSCD},

url = {https://doi.org/10.4230/LIPIcs.FSCD.2020.26}

}

[Dundua]

### Constraint Solving over Multiple Similarity Relations

#### Besik Dundua, Temur Kutsia, Mircea Marin, Cleopatra Pau

In: Proceedings of the 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020), Zena M. Ariola (ed.), Leibniz International Proceedings in Informatics (LIPIcs) 167, pp. 30:1-30:19. 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, ISBN 978-3-95977-155-9, ISSN 1868-8969. [url]@

author = {Besik Dundua and Temur Kutsia and Mircea Marin and Cleopatra Pau},

title = {{Constraint Solving over Multiple Similarity Relations}},

booktitle = {{Proceedings of the 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)}},

language = {english},

series = {Leibniz International Proceedings in Informatics (LIPIcs)},

volume = {167},

pages = {30:1--30:19},

publisher = {Schloss Dagstuhl--Leibniz-Zentrum für Informatik},

isbn_issn = {ISBN 978-3-95977-155-9, ISSN 1868-8969},

year = {2020},

editor = {Zena M. Ariola},

refereed = {yes},

length = {19},

url = {https://doi.org/10.4230/LIPIcs.FSCD.2020.30}

}

**inproceedings**{RISC6133,author = {Besik Dundua and Temur Kutsia and Mircea Marin and Cleopatra Pau},

title = {{Constraint Solving over Multiple Similarity Relations}},

booktitle = {{Proceedings of the 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)}},

language = {english},

series = {Leibniz International Proceedings in Informatics (LIPIcs)},

volume = {167},

pages = {30:1--30:19},

publisher = {Schloss Dagstuhl--Leibniz-Zentrum für Informatik},

isbn_issn = {ISBN 978-3-95977-155-9, ISSN 1868-8969},

year = {2020},

editor = {Zena M. Ariola},

refereed = {yes},

length = {19},

url = {https://doi.org/10.4230/LIPIcs.FSCD.2020.30}

}

[Dundua]

### Specification and Analysis of ABAC Policies in a Rule-Based Framework

#### Besik Dundua, Temur Kutsia, Mircea Marin, Mikheil Rukhaia

In: AMINSE 2019: Applications of Mathematics and Informatics in Natural Sciences and Engineering, George Jaiani, David Natroshvili (ed.), Springer Proceedings in Mathematics & Statistics 334, pp. 101-116. 2020. Springer, ISBN 978-3-030-56356-1, 978-3-030-56355-4. [url] [pdf]@

author = {Besik Dundua and Temur Kutsia and Mircea Marin and Mikheil Rukhaia},

title = {{Specification and Analysis of ABAC Policies in a Rule-Based Framework}},

booktitle = {{AMINSE 2019: Applications of Mathematics and Informatics in Natural Sciences and Engineering}},

language = {english},

series = {Springer Proceedings in Mathematics & Statistics},

volume = {334},

pages = {101--116},

publisher = {Springer},

isbn_issn = {ISBN 978-3-030-56356-1, 978-3-030-56355-4},

year = {2020},

editor = {George Jaiani and David Natroshvili},

refereed = {yes},

length = {16},

url = {https://doi.org/10.1007/978-3-030-56356-1_7}

}

**incollection**{RISC6228,author = {Besik Dundua and Temur Kutsia and Mircea Marin and Mikheil Rukhaia},

title = {{Specification and Analysis of ABAC Policies in a Rule-Based Framework}},

booktitle = {{AMINSE 2019: Applications of Mathematics and Informatics in Natural Sciences and Engineering}},

language = {english},

series = {Springer Proceedings in Mathematics & Statistics},

volume = {334},

pages = {101--116},

publisher = {Springer},

isbn_issn = {ISBN 978-3-030-56356-1, 978-3-030-56355-4},

year = {2020},

editor = {George Jaiani and David Natroshvili},

refereed = {yes},

length = {16},

url = {https://doi.org/10.1007/978-3-030-56356-1_7}

}

[Dundua]

### A Rule-Based System for Computation and Deduction in Mathematica

#### Mircea Marin, Besik Dundua, Temur Kutsia

In: WRLA 2020: Rewriting Logic and Its Applications, Santiago Escobar, Narciso Martí-Oliet (ed.), Lecture Notes in Computer Science 12328, pp. 57-74. 2020. Springer, ISBN 978-3-030-63595-4, 978-3-030-63594-7. [url] [pdf]@

author = {Mircea Marin and Besik Dundua and Temur Kutsia},

title = {{A Rule-Based System for Computation and Deduction in Mathematica}},

booktitle = {{WRLA 2020: Rewriting Logic and Its Applications}},

language = {english},

series = { Lecture Notes in Computer Science},

volume = {12328},

pages = {57--74},

publisher = {Springer},

isbn_issn = {ISBN 978-3-030-63595-4, 978-3-030-63594-7},

year = {2020},

editor = {Santiago Escobar and Narciso Martí-Oliet},

refereed = {yes},

length = {18},

url = {https://doi.org/10.1007/978-3-030-63595-4_4}

}

**inproceedings**{RISC6229,author = {Mircea Marin and Besik Dundua and Temur Kutsia},

title = {{A Rule-Based System for Computation and Deduction in Mathematica}},

booktitle = {{WRLA 2020: Rewriting Logic and Its Applications}},

language = {english},

series = { Lecture Notes in Computer Science},

volume = {12328},

pages = {57--74},

publisher = {Springer},

isbn_issn = {ISBN 978-3-030-63595-4, 978-3-030-63594-7},

year = {2020},

editor = {Santiago Escobar and Narciso Martí-Oliet},

refereed = {yes},

length = {18},

url = {https://doi.org/10.1007/978-3-030-63595-4_4}

}

[Dundua]

### Extending the 𝜌Log Calculus with Proximity Relations

#### Besik Dundua, Temur Kutsia, Mircea Marin, Cleo Pau

In: AMINSE 2019: Applications of Mathematics and Informatics in Natural Sciences and Engineering, George Jaiani, David Natroshvili (ed.), Springer Proceedings in Mathematics & Statistics 334, pp. 83-100. 2020. Springer, ISBN 978-3-030-56356-1, 978-3-030-56355-4. [url] [pdf]@

author = {Besik Dundua and Temur Kutsia and Mircea Marin and Cleo Pau},

title = {{Extending the 𝜌Log Calculus with Proximity Relations}},

booktitle = {{AMINSE 2019: Applications of Mathematics and Informatics in Natural Sciences and Engineering}},

language = {english},

series = {Springer Proceedings in Mathematics & Statistics},

volume = {334},

pages = {83--100},

publisher = {Springer},

isbn_issn = {ISBN 978-3-030-56356-1, 978-3-030-56355-4},

year = {2020},

editor = {George Jaiani and David Natroshvili},

refereed = {yes},

length = {18},

url = {https://doi.org/10.1007/978-3-030-56356-1_6}

}

**incollection**{RISC6227,author = {Besik Dundua and Temur Kutsia and Mircea Marin and Cleo Pau},

title = {{Extending the 𝜌Log Calculus with Proximity Relations}},

booktitle = {{AMINSE 2019: Applications of Mathematics and Informatics in Natural Sciences and Engineering}},

language = {english},

series = {Springer Proceedings in Mathematics & Statistics},

volume = {334},

pages = {83--100},

publisher = {Springer},

isbn_issn = {ISBN 978-3-030-56356-1, 978-3-030-56355-4},

year = {2020},

editor = {George Jaiani and David Natroshvili},

refereed = {yes},

length = {18},

url = {https://doi.org/10.1007/978-3-030-56356-1_6}

}

[Kutsia]

### Proceedings of The 34th International Workshop on Unification, UNIF 2020

#### Temur Kutsia and Andrew M. Marshall (Editors)

Technical report no. 20-10 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Schloss Hagenberg, 4232 Hagenberg, Austria. 2020. [pdf]@

author = {Temur Kutsia and Andrew M. Marshall (Editors)},

title = {{Proceedings of The 34th International Workshop on Unification, UNIF 2020}},

language = {english},

number = {20-10},

year = {2020},

length = {82},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

**techreport**{RISC6129,author = {Temur Kutsia and Andrew M. Marshall (Editors)},

title = {{Proceedings of The 34th International Workshop on Unification, UNIF 2020}},

language = {english},

number = {20-10},

year = {2020},

length = {82},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

[Kutsia]

### Unification modulo alpha-equivalence in a mathematical assistant system

#### Temur Kutsia

Technical report no. 20-01 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Schloss Hagenberg, 4232 Hagenberg, Austria. 2020. [pdf]@

author = {Temur Kutsia},

title = {{Unification modulo alpha-equivalence in a mathematical assistant system}},

language = {english},

number = {20-01},

year = {2020},

length = {21},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

**techreport**{RISC6074,author = {Temur Kutsia},

title = {{Unification modulo alpha-equivalence in a mathematical assistant system}},

language = {english},

number = {20-01},

year = {2020},

length = {21},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

[Kutsia]

### Constructing orthogonal designs in powers of two via symbolic computation and rewriting techniques

#### Ilias Kotsireas, Temur Kutsia, Dimitris Simos

Annals of Mathematics and Artificial Intelligence 88(1), pp. 213-236. 2020. ISSN 1573-7470. [url] [pdf]@

author = {Ilias Kotsireas and Temur Kutsia and Dimitris Simos},

title = {{ Constructing orthogonal designs in powers of two via symbolic computation and rewriting techniques}},

language = {english},

journal = {Annals of Mathematics and Artificial Intelligence},

volume = {88},

number = {1},

pages = {213--236},

isbn_issn = {ISSN 1573-7470},

year = {2020},

refereed = {yes},

length = {24},

url = {https://doi.org/10.1007/s10472-018-9607-9}

}

**article**{RISC6116,author = {Ilias Kotsireas and Temur Kutsia and Dimitris Simos},

title = {{ Constructing orthogonal designs in powers of two via symbolic computation and rewriting techniques}},

language = {english},

journal = {Annals of Mathematics and Artificial Intelligence},

volume = {88},

number = {1},

pages = {213--236},

isbn_issn = {ISSN 1573-7470},

year = {2020},

refereed = {yes},

length = {24},

url = {https://doi.org/10.1007/s10472-018-9607-9}

}

### 2019

[Cerna]

### Higher-Order Pattern Generalization Modulo Equational Theories

#### David M. Cerna and Temur Kutsia

Submitted to the RISC Report Series. 2019. [pdf]@

author = {David M. Cerna and Temur Kutsia},

title = {{Higher-Order Pattern Generalization Modulo Equational Theories}},

language = {english},

abstract = {In this paper we address Three problems related to unital anti-unification. First, we develop a generalalgorithm based on a tree grammar representation of the set of computed generalizations. Secondlywe show that restricting the algorithm to computing linear generalizations only or to term signaturescontaining a single unital function results in a procedure which is minimal complete and Finitary.Thirdly, we show that when the term signature contains two unital functions, unital anti-unification isNullary.The algorithm does not depend on the number of idempotent function symbols in the input terms. Thelanguage generated by the grammar is the minimal complete set of generalizations of the givenanti-unification problem, which implies that idempotent anti-unification is infinitary.},

year = {2019},

length = {40},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

**techreport**{RISC5918,author = {David M. Cerna and Temur Kutsia},

title = {{Higher-Order Pattern Generalization Modulo Equational Theories}},

language = {english},

abstract = {In this paper we address Three problems related to unital anti-unification. First, we develop a generalalgorithm based on a tree grammar representation of the set of computed generalizations. Secondlywe show that restricting the algorithm to computing linear generalizations only or to term signaturescontaining a single unital function results in a procedure which is minimal complete and Finitary.Thirdly, we show that when the term signature contains two unital functions, unital anti-unification isNullary.The algorithm does not depend on the number of idempotent function symbols in the input terms. Thelanguage generated by the grammar is the minimal complete set of generalizations of the givenanti-unification problem, which implies that idempotent anti-unification is infinitary.},

year = {2019},

length = {40},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

[Cerna]

### A Generic Framework for Higher-Order Generalizations

#### David M. Cerna, Temur Kutsia

In: Proceedings of the 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019), Herman Geuvers (ed.), Leibniz International Proceedings in Informatics (LIPIcs) 131, pp. 10:1-10:19. 2019. Schloss Dagstuhl, ISSN 1868-8969. [url]@

author = {David M. Cerna and Temur Kutsia},

title = {{A Generic Framework for Higher-Order Generalizations}},

booktitle = {{Proceedings of the 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)}},

language = {english},

series = {Leibniz International Proceedings in Informatics (LIPIcs)},

volume = {131},

pages = {10:1--10:19},

publisher = {Schloss Dagstuhl},

isbn_issn = {ISSN 1868-8969},

year = {2019},

editor = {Herman Geuvers},

refereed = {yes},

length = {19},

url = {http://dx.doi.org/10.4230/LIPIcs.FSCD.2019.10}

}

**inproceedings**{RISC5947,author = {David M. Cerna and Temur Kutsia},

title = {{A Generic Framework for Higher-Order Generalizations}},

booktitle = {{Proceedings of the 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)}},

language = {english},

series = {Leibniz International Proceedings in Informatics (LIPIcs)},

volume = {131},

pages = {10:1--10:19},

publisher = {Schloss Dagstuhl},

isbn_issn = {ISSN 1868-8969},

year = {2019},

editor = {Herman Geuvers},

refereed = {yes},

length = {19},

url = {http://dx.doi.org/10.4230/LIPIcs.FSCD.2019.10}

}

[Cerna]

### Idempotent Anti-unification

#### David Cerna, Temur Kutsia

ACM Transactions on Computational Logic (TOCL) 21(2), pp. 10:1-10:32. 2019. ACM Press, ISSN 1529-3785. [url] [pdf]@

author = {David Cerna and Temur Kutsia},

title = {{Idempotent Anti-unification}},

language = {english},

journal = {ACM Transactions on Computational Logic (TOCL)},

volume = {21},

number = {2},

pages = {10:1--10:32},

publisher = {ACM Press},

isbn_issn = {ISSN 1529-3785},

year = {2019},

refereed = {yes},

length = {32},

url = {https://doi.org/10.1145/3359060}

}

**article**{RISC6023,author = {David Cerna and Temur Kutsia},

title = {{Idempotent Anti-unification}},

language = {english},

journal = {ACM Transactions on Computational Logic (TOCL)},

volume = {21},

number = {2},

pages = {10:1--10:32},

publisher = {ACM Press},

isbn_issn = {ISSN 1529-3785},

year = {2019},

refereed = {yes},

length = {32},

url = {https://doi.org/10.1145/3359060}

}

[Dundua]

### Variadic Equational Matching

#### Besik Dundua, Temur Kutsia, Mircea Marin

In: Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Cezary Kaliszyk, Edwin Brady, Andrea Kohlhase, Claudio Sacerdoti Coen (ed.), Lecture Notes in Computer Science 11617, pp. 77-92. 2019. Springer, ISBN 978-3-030-23249-8. [pdf]@

author = {Besik Dundua and Temur Kutsia and Mircea Marin},

title = {{Variadic Equational Matching}},

booktitle = {{Intelligent Computer Mathematics - 12th International Conference, CICM 2019}},

language = {english},

series = {Lecture Notes in Computer Science},

volume = {11617},

pages = {77--92},

publisher = {Springer},

isbn_issn = {ISBN 978-3-030-23249-8},

year = {2019},

editor = {Cezary Kaliszyk and Edwin Brady and Andrea Kohlhase and Claudio Sacerdoti Coen},

refereed = {yes},

length = {16}

}

**inproceedings**{RISC5948,author = {Besik Dundua and Temur Kutsia and Mircea Marin},

title = {{Variadic Equational Matching}},

booktitle = {{Intelligent Computer Mathematics - 12th International Conference, CICM 2019}},

language = {english},

series = {Lecture Notes in Computer Science},

volume = {11617},

pages = {77--92},

publisher = {Springer},

isbn_issn = {ISBN 978-3-030-23249-8},

year = {2019},

editor = {Cezary Kaliszyk and Edwin Brady and Andrea Kohlhase and Claudio Sacerdoti Coen},

refereed = {yes},

length = {16}

}

[Pau]

### Computing All Maximal Clique Partitions in a Graph

#### Temur Kutsia, Cleo Pau

Technical report no. 19-04 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Schloss Hagenberg, 4232 Hagenberg, Austria. 2019. [pdf]@

author = {Temur Kutsia and Cleo Pau},

title = {{Computing All Maximal Clique Partitions in a Graph}},

language = {english},

number = {19-04},

year = {2019},

length = {9},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

**techreport**{RISC5939,author = {Temur Kutsia and Cleo Pau},

title = {{Computing All Maximal Clique Partitions in a Graph}},

language = {english},

number = {19-04},

year = {2019},

length = {9},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

[Pau]

### Solving Proximity Constraints

#### Temur Kutsia, Cleo Pau

Technical report no. 19-06 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Schloss Hagenberg, 4232 Hagenberg, Austria. 2019. [pdf]@

author = {Temur Kutsia and Cleo Pau},

title = {{Solving Proximity Constraints}},

language = {english},

number = {19-06},

year = {2019},

length = {22},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

**techreport**{RISC5950,author = {Temur Kutsia and Cleo Pau},

title = {{Solving Proximity Constraints}},

language = {english},

number = {19-06},

year = {2019},

length = {22},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

[Pau]

### Matching and Generalization Modulo Proximity and Tolerance

#### Temur Kutsia, Cleo Pau

Technical report no. 19-07 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Schloss Hagenberg, 4232 Hagenberg, Austria. 2019. [pdf]@

author = {Temur Kutsia and Cleo Pau},

title = {{Matching and Generalization Modulo Proximity and Tolerance}},

language = {english},

number = {19-07},

year = {2019},

length = {5},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

**techreport**{RISC5953,author = {Temur Kutsia and Cleo Pau},

title = {{Matching and Generalization Modulo Proximity and Tolerance}},

language = {english},

number = {19-07},

year = {2019},

length = {5},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

[Pau]

### Solving Proximity Constraints

#### Temur Kutsia, Cleo Pau

In: Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019. Revised Selected Papers, Maurizio Gabbrielli (ed.), Lecture Notes in Computer Science 12042, pp. 107-122. 2019. ISBN 978-3-030-45259-9. [pdf]@

author = {Temur Kutsia and Cleo Pau},

title = {{Solving Proximity Constraints}},

booktitle = {{Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019. Revised Selected Papers}},

language = {english},

series = {Lecture Notes in Computer Science },

volume = {12042},

pages = {107--122},

isbn_issn = {ISBN 978-3-030-45259-9},

year = {2019},

editor = {Maurizio Gabbrielli},

refereed = {yes},

length = {16}

}

**inproceedings**{RISC6100,author = {Temur Kutsia and Cleo Pau},

title = {{Solving Proximity Constraints}},

booktitle = {{Logic-Based Program Synthesis and Transformation - 29th International Symposium, LOPSTR 2019. Revised Selected Papers}},

language = {english},

series = {Lecture Notes in Computer Science },

volume = {12042},

pages = {107--122},

isbn_issn = {ISBN 978-3-030-45259-9},

year = {2019},

editor = {Maurizio Gabbrielli},

refereed = {yes},

length = {16}

}

### 2018

[Amiridze]

### Anti-Unification and Natural Language Processing

#### N. Amiridze, T. Kutsia

In: Fifth Workshop on Natural Language and Computer Science, NLCS’18, A. Asudeh, V. de Paiva, L. Moss (ed.), EasyChair preprints 203, pp. 1-12. 2018. [url] [pdf]@

author = {N. Amiridze and T. Kutsia},

title = {{Anti-Unification and Natural Language Processing}},

booktitle = {{Fifth Workshop on Natural Language and Computer Science, NLCS’18}},

language = {english},

series = {EasyChair preprints},

number = {203},

pages = {1--12},

isbn_issn = { },

year = {2018},

editor = {A. Asudeh and V. de Paiva and L. Moss},

refereed = {yes},

length = {12},

url = {https://doi.org/10.29007/fkrh}

}

**inproceedings**{RISC5707,author = {N. Amiridze and T. Kutsia},

title = {{Anti-Unification and Natural Language Processing}},

booktitle = {{Fifth Workshop on Natural Language and Computer Science, NLCS’18}},

language = {english},

series = {EasyChair preprints},

number = {203},

pages = {1--12},

isbn_issn = { },

year = {2018},

editor = {A. Asudeh and V. de Paiva and L. Moss},

refereed = {yes},

length = {12},

url = {https://doi.org/10.29007/fkrh}

}

[Baumgartner]

### Term-Graph Anti-Unification

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

Technical report no. 18-02 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Schloss Hagenberg, 4232 Hagenberg, Austria. 2018. [pdf]@

author = {Alexander Baumgartner and Temur Kutsia and Jordi Levy and Mateu Villaret},

title = {{Term-Graph Anti-Unification}},

language = {english},

number = {18-02},

year = {2018},

length = {19},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

**techreport**{RISC5549,author = {Alexander Baumgartner and Temur Kutsia and Jordi Levy and Mateu Villaret},

title = {{Term-Graph Anti-Unification}},

language = {english},

number = {18-02},

year = {2018},

length = {19},

type = {RISC Report Series},

institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},

address = {Schloss Hagenberg, 4232 Hagenberg, Austria}

}

[Cerna]

### Primitive Recursive Proof Systems for Arithmetic

#### David M. Cerna

RISC. Technical report, January 2018. In revision. [pdf] [pdf]@

author = {David M. Cerna},

title = {{Primitive Recursive Proof Systems for Arithmetic}},

language = {english},

abstract = {Peano arithmetic, as formalized by Gentzen, can be presented as an axiom extensionof the LK-calculus with equality and an additional inference rule formalizing induction.While this formalism was enough (with the addition of some meta-theoretic argumentation)to show the consistency of arithmetic, alternative formulations of induction such asthe infinitary ω-rule and cyclic reasoning provide insight into the structure of arithmeticproofs obfuscated by the inference rule formulation of induction. For example, questionsconcerning the elimination of cut, consistency, and proof shape are given more clarity. Thesame could be said for functional interpretations of arithmetic such as system T whichenumerates the recursive functions provably total by arithmetic. A key feature of thesevariations on the formalization of arithmetic is that they get somewhat closer to formalizingthe concept of induction directly using the inferences of the LK-calculus, albeit byadding extra machinery at the meta-level. In this work we present a recursive sequentcalculus for arithmetic which can be syntactically translated into Gentzen formalism ofarithmetic and allows proof normalization to the LK-calculus with equality.},

year = {2018},

month = {January },

note = {In revision},

institution = {RISC},

length = {20}

}

**techreport**{RISC5528,author = {David M. Cerna},

title = {{Primitive Recursive Proof Systems for Arithmetic}},

language = {english},

abstract = {Peano arithmetic, as formalized by Gentzen, can be presented as an axiom extensionof the LK-calculus with equality and an additional inference rule formalizing induction.While this formalism was enough (with the addition of some meta-theoretic argumentation)to show the consistency of arithmetic, alternative formulations of induction such asthe infinitary ω-rule and cyclic reasoning provide insight into the structure of arithmeticproofs obfuscated by the inference rule formulation of induction. For example, questionsconcerning the elimination of cut, consistency, and proof shape are given more clarity. Thesame could be said for functional interpretations of arithmetic such as system T whichenumerates the recursive functions provably total by arithmetic. A key feature of thesevariations on the formalization of arithmetic is that they get somewhat closer to formalizingthe concept of induction directly using the inferences of the LK-calculus, albeit byadding extra machinery at the meta-level. In this work we present a recursive sequentcalculus for arithmetic which can be syntactically translated into Gentzen formalism ofarithmetic and allows proof normalization to the LK-calculus with equality.},

year = {2018},

month = {January },

note = {In revision},

institution = {RISC},

length = {20}

}

[Cerna]

### Idempotent Anti-unification

#### David M. Cerna, Temur Kutsia

RISC. Technical report, Feb. 2018. to appear in TOCL. [pdf]@

author = {David M. Cerna and Temur Kutsia},

title = {{Idempotent Anti-unification }},

language = {english},

abstract = {In this paper we address two problems related to idempotent anti-unification. First, we show thatthere exists an anti-unification problem with a single idempotent symbol which has an infiniteminimal complete set of generalizations. It means that anti-unification with a single idempotentsymbol has infinitary or nullary generalization type, similar to anti-unification with two idem-potent symbols, shown earlier by Loı̈c Pottier. Next, we develop an algorithm, which takes anarbitrary idempotent anti-unification problem and computes a representation of its solution set inthe form of a regular tree grammar. The algorithm does not depend on the number of idempotentfunction symbols in the input terms. The language generated by the grammar is the minimalcomplete set of generalizations of the given anti-unification problem, which implies that idem-potent anti-unification is infinitary.},

year = {2018},

month = {Feb.},

note = {to appear in TOCL},

institution = {RISC},

length = {32}

}

**techreport**{RISC5530,author = {David M. Cerna and Temur Kutsia},

title = {{Idempotent Anti-unification }},

language = {english},

abstract = {In this paper we address two problems related to idempotent anti-unification. First, we show thatthere exists an anti-unification problem with a single idempotent symbol which has an infiniteminimal complete set of generalizations. It means that anti-unification with a single idempotentsymbol has infinitary or nullary generalization type, similar to anti-unification with two idem-potent symbols, shown earlier by Loı̈c Pottier. Next, we develop an algorithm, which takes anarbitrary idempotent anti-unification problem and computes a representation of its solution set inthe form of a regular tree grammar. The algorithm does not depend on the number of idempotentfunction symbols in the input terms. The language generated by the grammar is the minimalcomplete set of generalizations of the given anti-unification problem, which implies that idem-potent anti-unification is infinitary.},

year = {2018},

month = {Feb.},

note = {to appear in TOCL},

institution = {RISC},

length = {32}

}