Functions-as-constructors Higher-order Unification

Tomer Libal 1, 2 Dale Miller 2, 1
1 PARSIFAL - Proof search and reasoning with logic specifications
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : Unification is a central operation in the construction of a range of computational logic systems based on first-order and higher-order logics. First-order unification has a number of properties that dominates the way it is incorporated within such systems. In particular, first-order unification is decidable, unary, and can be performed on untyped term structures. None of these three properties hold for full higher-order unification: unification is undecidable, unifiers can be incomparable, and term-level typing can dominate the search for unifiers. The so-called pattern subset of higher-order unification was designed to be a small extension to first-order unification that respected the basic laws governing λ-binding (the equalities of α, β, and η-conversion) but which also satisfied those three properties. While the pattern fragment of higher-order unification has been popular in various implemented systems and in various theoretical considerations, it is too weak for a number of applications. In this paper, we define an extension of pattern unification that is motivated by some existing applications and which satisfies these three properties. The main idea behind this extension is that the arguments to a higher-order, free variable can be more than just distinct bound variables: they can also be terms constructed from (sufficient numbers of) such variables using term constructors and where no argument is a subterm of any other argument. We show that this extension to pattern unification satisfies the three properties mentioned above.
Type de document :
Communication dans un congrès
1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016), Jun 2016, Porto, Portugal. Leibniz International Proceedings in Informatics (LIPIcs), pp.1 - 17, 2016, 〈10.4230/LIPIcs.FSCD.2016.26〉
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01379683
Contributeur : Tomer Libal <>
Soumis le : mardi 11 octobre 2016 - 21:54:27
Dernière modification le : mercredi 14 novembre 2018 - 16:14:01
Document(s) archivé(s) le : samedi 4 février 2017 - 19:40:46

Fichier

fscd16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Tomer Libal, Dale Miller. Functions-as-constructors Higher-order Unification. 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016), Jun 2016, Porto, Portugal. Leibniz International Proceedings in Informatics (LIPIcs), pp.1 - 17, 2016, 〈10.4230/LIPIcs.FSCD.2016.26〉. 〈hal-01379683〉

Partager

Métriques

Consultations de la notice

525

Téléchargements de fichiers

63