Nominal Unification Revisited

Christian Urban
(TU Munich, Germany)

Nominal unification calculates substitutions that make terms involving binders equal modulo alpha-equivalence. Although nominal unification can be seen as equivalent to Miller's higher-order pattern unification, it has properties, such as the use of first-order terms with names (as opposed to alpha-equivalence classes) and that no new names need to be generated during unification, which set it clearly apart from higher-order pattern unification. The purpose of this paper is to simplify a clunky proof from the original paper on nominal unification and to give an overview over some results about nominal unification.

In Maribel Fernandez: Proceedings 24th International Workshop on Unification (UNIF 2010), Edinburgh, United Kingdom, 14th July 2010, Electronic Proceedings in Theoretical Computer Science 42, pp. 1–11.
Published: 21st December 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.42.1 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org