[HTML][HTML] Unranked second-order anti-unification

A Baumgartner, T Kutsia - Information and Computation, 2017 - Elsevier
A Baumgartner, T Kutsia
Information and Computation, 2017Elsevier
In this work we study anti-unification for unranked terms and hedges, permitting context and
hedge variables. Hedges are sequences of unranked terms. The anti-unification problem of
two hedges s˜ and q˜ is concerned with finding their generalization, a hedge g˜ such that
both s˜ and q˜ are substitution instances of g˜. Second-order power is gained by using
context variables to generalize vertical differences at the input hedges. Hedge variables are
used to generalize horizontal differences. An anti-unification algorithm is presented, which …
In this work we study anti-unification for unranked terms and hedges, permitting context and hedge variables. Hedges are sequences of unranked terms. The anti-unification problem of two hedges s˜ and q˜ is concerned with finding their generalization, a hedge g˜ such that both s˜ and q˜ are substitution instances of g˜. Second-order power is gained by using context variables to generalize vertical differences at the input hedges. Hedge variables are used to generalize horizontal differences. An anti-unification algorithm is presented, which computes a generalization of input hedges and records all the differences. The algorithm is parametric by a skeleton computation function. For instance, we can compute a generalization of a skeleton which represents a constrained longest common subforest, or an agreement subhedge/subtree of the input hedges. The computation of the generalization is done in quadratic time.
Elsevier