Unranked second-order anti-unification

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.