Back to Search
Start Over
Order-sorted Equational Generalization Algorithm Revisited
- Source :
- Annals of Mathematics and Artificial Intelligence
- Publication Year :
- 2022
- Publisher :
- Springer-Verlag, 2022.
-
Abstract
- Generalization, also called anti-unification, is the dual of unification. A generalizer of two terms t and $t^{\prime }$ is a term $t^{\prime \prime }$ of which t and $t^{\prime }$ are substitution instances. The dual of most general equational unifiers is that of least general equational generalizers, i.e., most specific anti-instances modulo equations. In a previous work, we extended the classical untyped generalization algorithm to: (1) an order-sorted typed setting with sorts, subsorts, and subtype polymorphism; (2) work modulo equational theories, where function symbols can obey any combination of associativity, commutativity, and identity axioms (including the empty set of such axioms); and (3) the combination of both, which results in a modular, order-sorted equational generalization algorithm. However, Cerna and Kutsia showed that our algorithm is generally incomplete for the case of identity axioms and a counterexample was given. Furthermore, they proved that, in theories with two identity elements or more, generalization with identity axioms is generally nullary, yet it is finitary for both the linear and one-unital fragments, i.e., either solutions with repeated variables are disregarded or the considered theories are restricted to having just one function symbol with an identity or unit element. In this work, we show how we can easily extend our original inference system to cope with the non-linear fragment and identify a more general class than one–unit theories where generalization with identity axioms is finitary.
- Subjects :
- Class (set theory)
Generalization
Equational reasoning
Applied Mathematics
Rule-based languages
Empty set
Commutativity
Identity (music)
Prime (order theory)
Artificial Intelligence
Identity
Associativity
Finitary
Order-Sorted
Algorithm
Least general generalization
LENGUAJES Y SISTEMAS INFORMATICOS
Axiom
Counterexample
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Annals of Mathematics and Artificial Intelligence
- Accession number :
- edsair.doi.dedup.....651acc9cdc53e4717040f28535c4e425