Permissive nominal terms and their unification
Abstract. We introduce permissive nominal terms. Nominal terms extend first-order terms with binding. They lack properties of first- and higher-order terms: Terms must be reasoned on in a context of ‘freshness assumptions’; it is not always possible to ‘choose a fresh variable symbol’ for a nominal term; and it is not always possible to ‘alpha-convert a bound variable symbol’. Permissive nominal terms recover these ‘always fresh’ and ‘always alpha-rename’ properties. Freshness contexts are elided and the notion of unifier is based on substitution alone rather than on nominal terms’ notion of substitution plus freshness conditions. We prove that all expressivity of nominal unification is retained.
1 Introduction
Many formal languages feature variable binding: examples include -abstraction, quantification, and sets comprehension (). Binding is ubiquitous, because variables are there to be bound or substituted.
Variables cannot be bound in first-order terms (constructed from variables and term-formers). This motivates extensions of first-order syntax; logics where variables can be bound by function or predicate symbols [DHK02], rewriting on terms with binders [KvOvR93,MN98,FG07], and languages with datatypes with binders [PE88,Mil91,SPG03,HHP87,Pau90,CU04].
We will study nominal terms [UPG04]. These preserve the flavour of first-order terms and extend them to represent informal statements like
“If fv() then is -equivalent with []” and
“How can we choose and to make () equal to ()?”.
(We write fv() for the free variables of ; e.g. fv((.)
Nominal terms use a characteristic combination of features: two levels of variable (atoms and unknowns), freshness conditions, permutations, and a distinctive theory of -equivalence (see Section 6 or [UPG04] for details). The first statement above is rendered in nominal terms as the equality judgement # []]() . Here and denote atoms, which represent the ‘’ and ‘’; denotes an unknown, it represents the ‘’; # is a freshness side-condition, it represents the ‘ fv()’; () is a permutation meaning ‘map to and to ’, it represents the ‘[]’ (we assumed fv(), so this is possible).
Yet nominal terms from [UPG04] have some less attractive properties too:
Freshness contexts are not fixed so we must often prove properties of terms-in-freshness context. This is harder than reasoning just about terms.
We cannot always pick a fresh variable symbol and -rename a bound variable. For in the empty freshness context, there is — by definition of the empty freshness context — no such that #.1
We propose permissive nominal terms. An unknown takes the form where is a permission sort (Definition 3). Permission sorts are sets of atoms that are both infinite and co-infinite (see Definition 2; is co-finite when is infinite). Thus, we can always choose a fresh atom, always -convert (Definition 8, Lemma 12), -equivalence is independent of a freshness context (there is no freshness context), and the notion of unifier is based just on substitution rather than (as for nominal terms) a freshness context and a substitution.
We illustrate this with two examples; definitions are in the paper. comb is an infinite, co-infinite set of atoms. Suppose comb. Assume a binary term-former (function-symbol) for application. Then:
-equivalence is ‘if fv() then ([])’. In nominal terms this becomes # []]().2 In permissive nominal terms it becomes [] ]() .
It is not possible to -convert in the nominal term []; to do this, we must enrich the freshness context .
In permissive nominal terms, it is always possible to -convert in []; we can convert to any of the atoms not in comb .
‘Unify () with ()’ becomes in nominal terms ‘[][]() [][]()’ and has solution (# [) ]).
In permissive nominal terms it becomes ‘[][]() ][]()’ and has solution [ ].
Unification is the basis of rewriting and logic programming. Nominal terms have served as the basis of both [FG07,CU04]. Therefore, and following that work, in this paper we explore permissive nominal unification.
2 Permissive nominal terms
Fix a countably infinite set of atoms. We use a permutative convention that will range over distinct atoms. Fix a set of term-formers. f g h will range over distinct term-formers.
Examples of term-formers are symbols like lam, app, and forall. In the presence of rewrites or equational axioms we can make these term-formers ‘do’ something; in this paper, they are just ways of building terms with suggestive names.
Call co-infinite when is infinite. Fix an infinite, co-infinite set comb . A permission sort has the form (comb) for finite sets and . will range over permission sorts.
If and are permission sorts, so are and , and both and are infinite.
For each fix a disjoint countably infinite set of unknowns of sort . , , , will range over distinct unknowns of sort . If then there is no particular connection between and . will range over finite sets of unknowns (we use this from Section 4 onwards).
A permutation is a bijection on atoms such that () is finite. and will range over permutations (not necessarily distinct).
Write id for the identity permutation such that id( always. Write () for the swapping which maps to , to , and all other to themselves.
Define (permissive nominal) terms by:
We write for syntactic identity; when and denote identical terms.
Define a permutation action by:
If , define the pointwise action by: () . Define free atoms fa() and unknowns fV () by:
An intuition for fa() is ‘possible free atoms after instantiation’.
Let denote the partial function ‘ restricted to ’. Define -equivalence inductively by:
id and () () .
fa( fa().
is transitive, reflexive, and symmetric.
For any , there exist infinitely many such that fa(). As a corollary, for any and there exists infinitely many fresh (so fa()) such that for some , [] [].
The first part is by an easy induction on . We consider only the case : fa(, and infinitely many are such that . The corollary follows using (=[b]).
3 Substitutions
A substitution is a function from unknowns to terms such that fa(()) always (so in describes the ‘permission’ we have to instantiate , namely to terms with free atoms in ). , , , , will range over substitutions.3
Write id for the identity substitution mapping to id always. It will always be clear whether id means the identity substitution or permutation.
Suppose fa() . Write [] for the substitution such that []() and []( id for all other
Define a substitution action of substitutions on terms by:
fa() fa().
() ().
By a routine induction on using the definitions and Lemma 9.
If (() for all fV (), then .
Define composition by ()() (()).
()().
By induction on . We consider the case of , and use Lemma 16: ()() ()() (()) (()) (())
4 Support inclusion problems
Recall from Definition 13 that fa(()) fa(, and from Theorem 15 that instantiation must reduce the set of free atoms. We will exhibit an algorithm which, intuitively, solves the problem “please make fa() true” (Definition 27 and Lemma 25). In fact the algorithm calculates solutions that are most general, in a sense made formal in Theorem 32.
A support inclusion is a pair of a term and a permission sort. A support inclusion problem is a finite multiset of support inclusions; Inc will range over support inclusion problems. Call a solution to Inc when fa() for every Inc. Write Sol(Inc) for the solutions of Inc.
Define a simplification rewrite relation by:
If Inc then Sol(Inc Sol().
Support inclusion problem simplification is confluent and terminating. Write nf (Inc) for the unique -normal form of Inc.
(Sketch) Support inclusion problem simplification is strongly confluent (see, for instance [BN98]), hence it is confluent. It is not hard to define a notion of size on problems such that rewrite rules strictly reduce the size of the problem they act on; it follows that simplification is terminating.
Call Inc consistent when nf (Inc) for all atoms and permission sorts . Call Inc solvable when Sol(Inc) . Call Inc non-trivial when nf (Inc) .
If Inc is consistent then all inc nf (Inc) have the form where .
Define fV (Inc) by fV (IncfV () Inc.
Let range over finite sets of unknowns.
Suppose Inc is consistent. For every make a fixed but arbitrary choice of such that and nf (Inc).
We make our choice injectively; for distinct fV (Inc) and fV (Inc), we choose and distinct. It will be convenient to write for the set of our choices . Define a substitution by:
If Inc is consistent then Sol(Inc). (‘ solves Inc’.)
Suppose Inc -normal form. If Inc then ( id for an which, by construction, satisfies . The result follows.
More generally, if Inc is not a =-normal form then note that by Lemma 22 Sol(Inc Sol(nf (Inc)); we use the previous paragraph.
Inc is consistent if and only if Inc is solvable.
By Lemma 22 Sol(Inc Sol(nf (Inc)), so it suffices to show the result for the special case that Inc -normal form.
Suppose Inc is inconsistent, so nf () contains some support inclusions of the form where . always, so there is no substitution such that . Conversely, if Inc is consistent the result follows by Lemma 28.
Suppose that Inc is consistent, fV (Inc) , and Sol(Inc). Define a substitution - by:
– (-)() () if and () id .
– (-)() () if .
Suppose Sol(Inc) and fV (Inc) . Then exists, and - is a substitution.
If Sol(Inc) then Inc is solvable (Definition 20). By Theorem 29, Inc is consistent. Therefore from Definition 27 exists. We now show that fa((-)()) always. We reason by cases:
The case that id () for .
It is not hard to prove that fV (nf (Inc)) fV (Inc) always, so fV (nf (Inc)) . There are two sub-cases:
The case fV (nf (Inc)). Then and (-)(().
By assumption fa(()) .
The case fV (nf (Inc)). Sol(Inc) so by Lemma 22 Sol(nf (Inc)) and so fa(()) for every such that nf (Inc). By definition nf (Inc) and the result follows.
Otherwise, (-)() (). By assumption fa(()) .
Suppose Sol(Inc) and suppose fV (Inc) . Then () ( (-))() for every .
() id for some fresh , and (-)() (). The result follows by Lemma 9.
5 Permissive nominal unification problems
5.1 Problems, solutions, the unification algorithm
An equality (problem) is a pair . A problem is a finite multiset of equalities. Define by .
solves when implies . Write Sol() for the set of solutions to . Call solvable when Sol() is non-empty.
A solution to ‘makes the equalities valid’, as for first- and higher-order unification. This simplifies the nominal unification notion of solution (Definition 66 or [UPG04, Definition 3.1]) based on ‘a substitution + a freshness context’.
Sol() if and only if Sol().
Suppose Sol() and . We reason using Theorem 19: ()(() (). The reverse implication is similar.
If is a problem, define a support inclusion problem by: fa() fa() .
Define a simplification rewrite relation ; ; by:
Call (a), (f), (a]), (b]), and (X) non-instantiating rules.
Call (I1), (I2), and (I3) instantiating rules.
We insist is non-trivial (Definition 20) to avoid indefinite rewrites. We insist is consistent so exists. and are defined in Definition 27.
If by a non-instantiating rule then Sol( Sol().
The interesting case is (b]). Suppose that ]] and fa() and so () with (b]). Then:
Suppose ([]) ([]). By Definition 14 []( [](). By the structure of the rules in Definition 8, ()(. By Lemma 16 and Theorem 11, (() ).
Suppose (()). By Lemma 16 and Theorem 11, ()(. By Theorem 15 fa(). Therefore by (=[b]) []( [](). By Definition 14 []( [](), as required.
Define fV (fV () fV () .
Suppose is a set of unknowns. Define by:4
If is a problem, define a unification algorithm by:
1. Rewrite fV (); using the rules of Definition 37 as much as possible, with top-down precedence (so apply (a) before (f), and so on down to (I3)).
2. If we reduce to ; , we succeed and return where is the functional composition of all the substitutions labelling rewrites (we take id if there are none). Otherwise, we fail.
The algorithm of Definition 41 always terminates.
By an easy argument using a notion of the size of a unification problem.
Suppose (() for all fV (). Then Sol() if and only if Sol().
Write - for the substitution such that:
Suppose (id ) and fV (). Then:
We reason as follows:
5.2 Simplification rewrites calculate principal solutions
Write when there exists such that () always. We call the instantiation ordering.
A principal (or most general) solution to a problem is a solution Sol() such that for all other Sol().
Our main results are Theorems 48 — the unification algorithm from Definition 41 calculates a solution — and 53 — the solution it calculates, is principal.
Suppose fV () . If ; ; then Sol().
By induction on the length of the path in . If it has length 0 then and id and the result follows. Otherwise, there are three cases:
The non-instantiating case. Suppose ; ; ; . By easy calculations fV () . By inductive hypothesis Sol(). By Lemma 38, Sol().
The case of (I1) or (I2). Suppose ; ; ; . By easy calculations fV () . By inductive hypothesis Sol(). It is a fact that () (). By Lemma 35, () Sol().
The case of (I3). Suppose ; ; ; . By easy calculations fV () . By inductive hypothesis Sol(). By Lemma 35, () Sol(). It is a fact that (). By Lemma 43, () Sol().
If then .
Suppose always. Then implies .
If then fa( fa().
Using Lemma 51.
Suppose fV () . If ; ; then is a principal solution to .
By Theorem 48 Sol(). We prove that is principal by induction on the path length of ; ; .
Length 0. So and id. id is a fact of Definition 46.
Length . We consider the rules in Definition 37.
The non-instantiating case. Suppose ; ; ; where ; ; is non-instantiating. By inductive hypothesis, is a principal solution of . By Lemma 38 is also a principal solution of .
The case (I1). Suppose fa() and fV (). Write ]. Suppose so that ; ; and
suppose ; ; and Sol(). By Theorem 48 Sol(). It is routine to check that fV () . By Theorem 45 and Lemma 43, (-) Sol(). It is a fact that (--) so by Lemma 35, () Sol(). By inductive hypothesis (-). By Lemma 49 we have () (-). Now by assumption fV () and , and it follows that (). Also, it is a fact that ()-. By Theorem 45 and Lemma 50, () as required.
The case (I2) is similar to the case of (I1).
The case (I3). Suppose is consistent and non-trivial. Write ,
so that ; ; and ; ; and suppose Sol().
By Theorem 48 Sol(). , so fV () . By
Lemma 52 Sol(). By Theorem 32 and Lemma 43 it follows that (-) Sol(). By Lemma 35, - Sol(). By inductive hypothesis -. By Lemma 49 (-). It is a fact that (). By Theorem 32 and Lemma 50, () as required.
If ; ; with (I1) or (I2) then Sol() implies - Sol(). Similarly, if ; ; with (I3) then Sol() implies - Sol().
Suppose fa() and fV (). Write ]. Suppose so that ; ; . Now suppose Sol(). By Lemma 43 and Theorem 45, (-)) Sol(). By Lemma 35, - Sol(). It follows that - Sol() as required.
Suppose is consistent and non-trivial. Write , so that ; ; . Now suppose Sol(). By Lemma 43 and Theorem 32, (-) Sol(). By Lemma 35, - Sol() as required.
Given a problem , if the algorithm of Definition 41 succeeds then it returns a principal solution; if it fails then there is no solution.
If the algorithm succeeds we use Theorem 53. Otherwise, the algorithm generates an element of the form f() f() where , f() g(), f() ], f() , [], [], , a such that is inconsistent, or or where fV (). By arguments on syntax and size of syntax, no solution to the reduced problem exists. It follows by Lemma 54 that no solution to exists.
6 Relation to nominal terms
In permissive nominal terms, freshness information is fixed once and for all. This is mentioned already as a design alternative in [UPG04, Remark 2.6], but there, we would obtain ‘permission sorts’ such that is infinite and is finite. Permission sorts of co-infinite sets of atoms are new, as far as we know.
We will now develop the intuitively clear connection with [UPG04] into a precise mathematical correspondence between nominal unification and permissive nominal unification. Definition 59 translates from ‘nominal’ to ‘permissive’. Theorems 62 and 63 express how this translation is sound and complete for respective notions of -equivalence. Theorem 71 then shows the most interesting fact: that furthermore, solutions to unification problems are also preserved across the translation.
A feature of Definition 59 is that it maps nominal terms to permissive nominal terms with free atoms in comb. In nominal terms we may need to enrich the freshness context (see [GM07, Figure 2, axiom (fr)] and [GM09b, e.g. Lemma 25 and Theorem 33]). One way to view the interpretation of Definition 59 is therefore this: comb is ‘the atoms we had available so far’ (any other permission sort would do as well) and comb is ‘the atoms with which we will extend the freshness context, in the future’. Both these sets are countably infinite, and syntax is finite, so it is not absolutely necessary to explicitly separate them: permissive nominal terms do this, for each fixed permission sort ; nominal terms do not.
Fix a countably infinite set of nominal atoms, will range over distinct nominal atoms. Fix a bijection between and comb (Definition 2). Fix a countably infinite set of nominal unknowns. will range over distinct nominal unknowns. A nominal permutation is a bijection on such that ) is finite. will range over permutations.
Write for the inverse of , for the identity permutation, and for function composition, as is standard. For example, ( ))
Define nominal terms by f), with permutation action
Write for syntactic identity. f ranges over term-formers (Definition 1).
A freshness is a pair . An equality is a pair . A freshness context is a finite set of freshnesses of the form # . Define derivable freshness and derivable equality by:
Definition 58 repeats [UPG04, Figure 2], up to differences in presentation. A full discussion of nominal terms is in [UPG04]. corresponds with ‘ fa()’ (made formal in Lemma 61), and corresponds with ‘’ (see Theorems 62 and 63). plays the role of permissions sorts, but is part of the judgement-form.
Define a mapping from nominal permutations to permissive nominal permutations by ()) and ( for all comb. Define an interpretation by:
Here, we make a fixed but arbitrary choice of for each , injectively so that and are always distinct.
)fa() if and only if . fa() if comb.
implies .
If then .
A substitution is a function from nominal unknowns to nominal terms such that ( ) is finite. will range over nominal substitutions. Write for the identity, mapping to .
Define a substitution action on nominal terms by:
Following [UPG04, Definition 3.1], a unification problem is a finite multiset of freshnesses and equalities. A solution to is a pair ( ) such that for every , and for every .
We extend the interpretation of Definition 59 to solutions by:
( ) .
By inductions on . We consider the case , and reason using Lemma 60:
Define by mapping to and mapping to ()) , for some choice of fresh (so fa(); in fact, it suffices to choose some comb).
Suppose fa(). Then fa() if and only if () .
( ) solves if and only if () solves .
7 Conclusions
Nominal contrasted with permissive nominal terms. It can be problematic that in nominal terms [GM09b,GM08] we often want to enrich the freshness context, e.g. to -convert or in solving a unification problem. Also, it is unfortunate that we cannot ‘just quotient terms by -conversion’ since we cannot apply nominal abstract syntax [GP01] ... to nominal terms. Permissive nominal terms let us do all these things, and they behave more like first-order terms; we recover Lemma 12, -equivalence is a property of terms, and the notions of unification problem and solution involve just equality, not equality-and-freshness-context.
The step from permissive nominal terms to nominal terms makes a remarkably big difference. This has implications for developing nominal techniques further; we believe that in many situations, permissive nominal terms may be easier to work with and better-behaved. By Definition 59 and Theorem 71, there is no loss in expressivity.
Permissive nominal terms do not necessarily obsolete nominal terms; if we really do want to discuss ‘an arbitrary term’, then the nominal terms unknown from Section 6 may be more simply and directly useful than . One possibly interesting extension of permissive nominal terms, is with variables for permission sorts.
Note that the unification algorithm in [UPG04] solves freshnesses concurrently with equalities. We have factored the algorithm differently, so that problems to do with free atoms (Section 4) are solved separately from problems to do with equalities (Section 5). The link is rule (I3) in Definition 37.
Concerning implementation, permissive nominal terms are implementable. Sorts are infinite sets of atoms, but differ finitely from comb and so may be finitely represented in an implementation.
Related work not based on nominal techniques. Permissive nominal terms resemble first- and higher-order terms more than do nominal terms, but they are a special case of neither. Higher-order patterns also have good properties of first-order terms [Mil91]. A significant difference is that the notion of unification is based on capture-avoiding substitution rather than the (permissive) nominal term capturing substitution; this gives the system a different flavour. The reader is referred to a recent paper [LV08], which goes some way to teasing out formal connections between these two approaches.
Permission sorts can be compared with the types used in [DHK00] and fully developed in [NPP07] that indicate the atoms that may appear in a term.
Hamana’s unification of -terms with holes adds a capturing substitution [Ham01]. Level 2 variables (which are instantiated) are annotated with level 1 variable symbols that may appear in them; permissive nominal terms move in this direction in the sense that permission sorts also describe which level 1 variable symbols (we call them atoms in this paper) may appear in them, though with our permission sorts there are infinitely many that may, and infinitely many that may not. The treatment of -equivalence in Hamana’s system is not nominal (not based on permutations) and Hamana’s system does not have most general unifiers. Similarly Qu-Prolog [NR96] adds level 2 variables, but does not manage -conversion in nominal style and also, for better or for worse, it is more ambitious in what it expresses and loses mathematical properties (unification is semi-decidable, most general unifiers need not exist).
Future work. We have investigated how the instantiation ordering interacts with the interpretation of Section 6. Most general solutions of nominal unification problems in the sense of [UPG04, Definition 3.1] do translate to most general solutions of the translated problem, in the sense of Definition 46. It is also possible to leverage permissive nominal terms to improve on the correspondence between nominal unification and Miller’s pattern unification [Mil92,Mil91] reported on in [LV08]; in [LV08] only solvability is considered, but permissive nominal terms’ good properties can be applied to give a particularly neat translation of solutions between permissive nominal unification and higher-order pattern unification. These results with full proofs will be reported in a journal version of this paper.
We hypothesise that ‘permissive’ versions of nominal rewriting, logic programming, and algebra, should be possible, following previous work using nominal terms [FG07,CU03,GM07,GM09a]. On this topic, addressing a point by Fernández, suppose comb; then the rewrite cannot trigger the rewrite because there is no such that comb comb , and likewise there is no substitution , because of the side-condition that fa(()) comb. It may therefore be desirable to consider only permissions sorts of the form comb for finite. This is not a problem for unification and the proofs in this paper because they do not ‘add’ atoms to permissions sorts (we only ever need to ‘subtract’ them, as in Section 4). Alternatively, as mentioned above, we could consider permissive nominal terms syntax with variables ranging over permissions sorts.
References
BN98. Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, Great Britain, 1998.
CU03. J. Cheney and C. Urban. System description: Alpha-Prolog, a fresh approach to logic programming modulo alpha-equivalence. In UNIF’03, pages 15–19. Universidad Politecnica de Valencia, 2003.
CU04. James Cheney and Christian Urban. Alpha-prolog: A logic programming language with names, binding and alpha-equivalence. In Bart Demoen and Vladimir Lifschitz, editors, Proc. of the 20th Int’l Conf. on Logic Programming (ICLP 2004), number 3132 in Lecture Notes in Computer Science, pages 269–283. Springer, 2004.
DHK00. G. Dowek, Th. Hardin, and C. Kirchner. Higher-order unification via explicit substitutions. Information and Computation, 157, 2000.
DHK02. Gilles Dowek, Thérèse Hardin, and Claude Kirchner. Binding logic: Proofs and models. In LPAR ’02: Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, pages 130–144, London, UK, 2002. Springer.
FG07. Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, 2007.
GM07. Murdoch J. Gabbay and Aad Mathijssen. A formal calculus for informal equality with binding. In Proceedings of 14 Workshop on Logic, Language and Information in Computation (WoLLIC 2007), volume 4576 of Lecture Notes in Computer Science, pages 162–176, 2007.
GM08. Murdoch J. Gabbay and Dominic P. Mulligan. One-and-a-halfth Order Terms: Curry-Howard for Incomplete Derivations. In Proceedings of 15 Workshop on Logic, Language and Information in Computation (WoLLIC 2008), volume 5110 of Lecture Notes in Artificial Intelligence, pages 180–194, 2008.
GM09a. Murdoch J. Gabbay and Aad Mathijssen. Nominal (universal) algebra: equational logic with names and binders. Journal of Logic and Computation, 2009. Accepted subject to revision.
GM09b. Murdoch J. Gabbay and Dominic P. Mulligan. Two-and-a-halfth Order Lambda-calculus. Electronic Notes in Theoretical Computer Science, 2009. To appear.
GP01. Murdoch J. Gabbay and A. M. Pitts. A New Approach to Abstract Syntax with Variable Binding (journal version). Formal Aspects of Computing, 13(3–5):341–363, 2001.
Ham01. Makoto Hamana. A logic programming language based on binding algebras. In TACS’01, volume 2215 of Lecture Notes in Computer Science, pages 243–262. Springer, 2001.
HHP87. Robert Harper, Furio Honsell, and Gordon Plotkin. A framework for defining logics. In Proc. 2nd Annual IEEE Symposium on Logic in Computer Science, LICS’87, pages 194–204. IEEE Computer Society Press, 1987.
KvOvR93. J.-W. Klop, V. van Oostrom, and F. van Raamsdonk. Combinatory reduction systems. Theoretical Computer Science, 121:279–308, 1993.
LV08. Jordi Levy and Mateu Villaret. Nominal unification from a higher-order perspective. In Proceedings of RTA’08, volume 5117 of Lecture Notes in Computer Science, pages 246–260. Springer, 2008.
Mil91. Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation, 1(4):497–536, 1991.
Mil92. Dale Miller. Unification under a mixed prefix. Journal of Symbolic Computation, 14(4):321–358, 1992.
MN98. Richard Mayr and Tobias Nipkow. Higher-order rewrite systems and their confluence. Theoretical Computer Science, 192:3–29, 1998.
NPP07. Aleksandar Nanevski, Frank Pfenning, and Brigitte Pientka. Contextual modal type theory. Transactions on Computational Logic, 2007.
NR96. Peter Nickolas and Peter J. Robinson. The Qu-Prolog unification algorithm: formalisation and correctness. Theoretical Computer Science, 169(1):81–112, 1996.
Pau90. Lawrence C. Paulson. Isabelle: the next 700 theorem provers. In P. Odifreddi, editor, Logic and Computer Science, pages 361–386. Academic Press, 1990.
PE88. F. Pfenning and C. Elliot. Higher-order abstract syntax. In PLDI (Programming Language design and Implementation), pages 199–208. ACM Press, 1988.
SPG03. M. R. Shinwell, A. M. Pitts, and Murdoch J. Gabbay. FreshML: Programming with Binders Made Simple. In ICFP’03, volume 38, pages 263–274. ACM Press, 2003.
UPG04. Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, 2004.
Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.
Notes
1 ‘Freshness contexts’ sounds like ‘typing contexts’, but the terminology misleads. Extending a typing context makes more terms typable and, intuitively, extends the universe of discourse with extra typable terms. Extending a freshness context makes more terms equal. This is a more drastic event because it is more likely to change the behaviour of existing elements; they may now be equal to other elements with quite different behaviour. ↩
2 In the body of the paper we put dots on atoms and unknowns in nominal terms, to emphasise the difference from permissive nominal terms. Here, we do not bother. ↩
3 ‘fa(()) ’ looks absent in nominal terms theory ([UPG04, Definition 2.13], [FG07, Definition 4]), yet it is there: see the conditions ‘()’ in Lemma 2.14, and ‘#()’ in Definition 3.1 of [UPG04]. More on this in Section 6. ↩
4 We overload , for technical convenience: (Definition 8) is partial and is total. ↩