RISC RISC Research Institute for Symbolic Computation  
  • @techreport{RISC5530,
    author = {David M. Cerna Temur Kutsia},
    title = {{Anti-unification problems with one idempotent symbol can have infinitely many solutions}},
    language = {english},
    abstract = {In ``Generalisation de termes en theorie equationnelle. Cas associatif-commutatif'', an example was given of a pair of terms constructed using two idempotent function symbols (that is a binary symbol $f$ s.t. the following equivalence holds, $f(x,x)=x$) which allow for an infinite number of incomparable least general generalizations. The terms themselves are simple, namely $f(a,b)$ and $g(a,b)$ where $a$ and $b$ are constants and $f$ and $g$ are idempotent functions. We show that this example can be encoded using a single idempotent function symbol and thus it entails that idempotent generalization allows for an infinite number of incomparable least general generalizations if there are at least two incomparable least general generalizations in the solution set.},
    year = {2018},
    month = {Feb.},
    institution = {RISC},
    length = {4}