Generalization Problems with Atom-Variables in Languages with Binders and Equational Theories
Daniele Nantes-Sobrinho, Manfred Schmidt-Schauß, Alexander Baumgartner, Temur Kutsia · 2025
Read Generalization Problems with Atom-Variables in Languages with Binders and Equational Theories by Daniele Nantes-Sobrinho, Manfred Schmidt-Schauß, Alexander Baumgartner, Temur Kutsia (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-19306.txt.
Description
Daniele Nantes-Sobrinho and three co-authors solve generalization problems in logic in twenty twenty-five. Generalization means finding the most common structure shared by expressions. In languages with binders, bound variable names can be renamed, which complicates the search. Such problems often have no single least general solution.
Using nominal techniques with atom-variables, the team had earlier removed redundant solutions. That gave unique least general generalizations in the plain case. This work extends the approach to equational theories. It handles associative, commutative, and combined forms of equality. Their algorithm is sound and weakly complete, producing finite sets of generalizations. A key hurdle is solving equivariance problems under those same theories.
Catalog record
| CREATOR | Daniele Nantes-Sobrinho, Manfred Schmidt-Schauß, Alexander Baumgartner, Temur Kutsia |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-19306