Order-sorted equational generalization algorithm revisited

María Alpuente, Santiago Escobar, José Meseguer, Julia Sapiña

Research output: Contribution to journalArticlepeer-review


Generalization, also called anti-unification, is the dual of unification. A generalizer of two terms t and t is a term t of which t and t 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.

Original languageEnglish (US)
Pages (from-to)499-522
Number of pages24
JournalAnnals of Mathematics and Artificial Intelligence
Issue number5
StatePublished - May 2022


  • Associativity
  • Commutativity
  • Equational reasoning
  • Identity
  • Least general generalization
  • Order-Sorted
  • Rule–based languages

ASJC Scopus subject areas

  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Order-sorted equational generalization algorithm revisited'. Together they form a unique fingerprint.

Cite this