Relating higher-order pattern unification and nominal unification

By James Cheney, from UNIF 2005, available from James Cheney’s website:

Higher-order pattern unification and nominal unification are two approaches to unifying modulo some form of α-equivalence (consistent renaming of bound names). The higher-order and nominal approaches seem superficially dissimilar. However, we show that a natural concretion (or name-application) operation for nominal terms can be used to simulate the behavior of higher-order patterns. We describe a form of nominal terms called nominal patterns that includes concretion and for which unification is equivalent to a special case of higher-order pattern unification, and then show that full higher-order pattern unification can be reduced to nominal unification via nominal patterns.

This is one in a series of three papers detailing the precise connection between higher-order pattern unification and nominal unification (they’re essentially “the same thing”).  Levy and Villaret expanded on Cheney’s work, removing the need for the translation to nominal patterns, with the concretion operator.  They demonstrated that higher-order pattern unifiability is preserved under their translation.  However, Dowek and Gabbay took Levy and Villaret’s results further, and came up with a translation where higher-order unifiers are preserved (they also sharpened Levy and Villaret’s result in another direction, by demonstrating that the Dowek/Gabbay translation is optimum, in a certain manner).

EDIT: the Dowek/Gabbay conference paper isn’t yet available, though the material from that paper will be in a journal paper “Permissive nominal terms and their unification” by Dowek, Gabbay and Mulligan, hopefully to appear soon.  If you have access to the ACM academic archive, then the Levy and Villaret paper is available here.

0 Responses to “Relating higher-order pattern unification and nominal unification”



  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s





%d bloggers like this: