|Title||Nominal Unification from a Higher-Order Perspective|
|Publication Type||Journal Article|
|Year of Publication||2012|
|Authors||Levy J, Villaret M|
|Journal||ACM Transactions on Computational Logics|
Nominal logic is an extension of first-order logic with equality, name-binding, renaming via name-swapping and freshness of names. Contrarily to lambda-terms, in nominal terms, bindable names, called atoms, and instantiable variables are considered as distinct entities. Moreover, atoms are capturable by instantiations, breaking a fundamental principle of the lambda-calculus. Despite these differences, nominal unification can be seen from a higher-order perspective. From this view, we show that nominal unification can be quadratically reduced to a particular fragment of higher-order unification problems: higher-order pattern unification. We also prove that the translation preserves most generality of unifiers.
- About IIIA
- Current news