Permissive nominal terms and their unification
ahttp://www.lix.polytechnique.fr/~dowek
bhttp://www.gabbay.org.uk
chttp://www.macs.hw.ac.uk/~dpm8
Abstract
We introduce permissive nominal terms, and their unification.
Nominal terms are one way to extend first-order terms with binding. However, they lack some useful properties of first- and higher-order terms: Terms must be reasoned about 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 ‘-convert a bound variable symbol’.
Permissive nominal terms closely resemble nominal terms, but they recover these useful ‘always fresh’ and ‘always alpha-rename’ properties, familiar from first- and higher-order syntax. In the permissive world, 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 expressivity is not lost moving to the permissive case. We provide a translation from nominal terms into permissive nominal terms and we prove that a nominal unification problem is solvable if and only if its translation into permissive nominal terms is.
Finally, we investigate the precise relation between nominal unification and Miller’s higher-order pattern unification. We translate nominal terms into the -calculus and show that the translation may also be applied to unification problems; the result is pattern unification. This cements an existing intuition that higher-order patterns are what is needed to unify encodings of nominal terms. This builds on a translation by Levy and Villaret, and refines it; both translations are parameterised by sets of atoms, but we identify a smaller parameter set and prove that it is as small as possible. We also translate solutions of nominal unification problems to solutions of higher-order pattern unification problems. We exhibit a general class of higher-order pattern solutions and show that every pattern solution in that class is the translation of a nominal unification solution up to a permutative renaming.
Key words: Nominal unification, higher-order pattern unification, nominal techniques
February 25, 2009
1. Introduction
Many formal languages feature variable binding: examples include quantification, -abstraction, sets comprehension
In contrast, variables cannot be bound in first-order terms: In first-order logic, variables are bound in propositions by quantifiers and not at all in terms; first-order rewriting does not allow binding as it is based on first-order terms; and, many programming languages and proof systems allow datatypes of terms, but only of first-order terms. This motivates logics where variables can be bound by any function or predicate symbol [8], extensions of rewriting on terms with binders [18, 20, 9], and programming languages and proof systems allowing datatypes with binders [25, 21, 26, 17, 24] and more generally, definitions of a notion of term where variables may be bound: nominal terms [27].
Introducing binding opens new possibilities: when a variable occurs in the scope of a binder, for instance in the term ([]) we may decide that the substitution of some term for may capture the bound variable or not. In the original formulation of nominal terms, we could decide to exclude this capture by imposing a condition #, forbidding to appear in . This example explains some of the features of nominal terms: two levels of variable (atoms, such as , and unknowns, such as ), freshness conditions, such as #, and atom permutations.
Nominal terms preserved much of the flavour of first-order terms, while extending them, so that we could represent informal statements like “If fv() then is -equivalent with []” and “How can we choose and to make () equal to ()?”. For instance, the first statement above may be rendered as a nominal term as the equality judgement #
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 expect that we can always pick a fresh variable symbol and -rename a bound variable. Not so in nominal terms; for in the empty freshness context, there is
— by definition of the empty freshness context — no such that we know #; further, we cannot -rename abstracted to a ‘fresh ’ to obtain [](), because there is no fresh (this is useful e.g. for moving syntax under a binder). ‘Freshness contexts’ sound like ‘typing contexts’ for the -calculus, but freshness contexts’ effects are more complex and harder to control. Extending a typing context may make more terms typable, but will not typically make more terms equal; -equivalence is independent of typing, but it depends on freshness. This then complicates, for example, normal forms and theories of reduction (lack of -convertibility may block a reduction; adding a fresh atom may change the normal form of a term) as is explicit in [13], and implicit e.g. in [12, 11].
In this paper, we propose an alternative way to handle these conditions by associating a freshness context once and for all to each unknown. This leads to a new definition of nominal terms: permissive nominal terms. An unknown takes the form where is a single fixed permission sort (Definition 3); thus, we can reason about terms, rather than about terms-in-freshness-context. In a further departure from the usual nominal style, permission sorts are sets of atoms that are both infinite and co-infinite (see Definition 2). Thus, we can always choose a fresh atom for a term, always -convert, and -equivalence is inherent rather than depending on a freshness context (Definition 11, Theorem 13, and Corollary 14).
Permissive nominal terms allow to simplify several results and algorithms of the theory of nominal terms, in particular their unification. The solutions of a problem, such as () , is the set of all substitutions mapping the variable to a term containing no occurrences of and . The unifier of such a problem is simply the substitution where .
Thus, after laying down definitions and basic properties of permissive nominal terms (Sections 2 and 3) and studying their relation to original nominal terms (Section 4), we focus on the unification of permissive nominal terms (Sections 5 and 6).
The rest of the paper considers translations of permissive nominal terms. It is known that languages containing binders can be encoded as datatypes in some programming languages and proof systems using -binding and higher-order abstract syntax [25]. We investigate this idea in the general form of a translation of permissive nominal terms to -calculus (Section 8). Finally, building up on a recent result of Levy and Villaret, we show (Section 9) that this translation can be applied to unification problems and yields pattern unification problems, as identified by Miller [22, 21], crystallizing the intuition that pattern unification is exactly what is needed to unify encodings of nominal terms.
Levy and Villaret’s main result is that a nominal unification problem is solvable if and only if its translation into higher-order patterns, is solvable [19, Corollary 1 and Theorem 2]. We take this further as follows:
We investigate how the solutions of a problem, and the solutions of its translation, correspond. We translate terms and substitutions from the ‘nominal’ to the ‘higher-order pattern’ world (Definitions 117 and 129) and show that the translation of a solution is a solution of the translation (Theorem 141).
We exhibit a general class of higher-order pattern solutions (Definition 149), a notion of permutative renaming of pattern substitutions (Lemma 147), and show that every pattern substitution in that class is the translation of a nominal unification solution, up to permutative renaming (Theorem 155).
We refine Levy and Villaret’s translation of terms. Their translation is parameterised by a vector of atoms; Levy and Villaret consider a vector containing all the atoms of the problem [19, Definition 2], whereas we identify a smaller vector containing only the capturable atoms (Definition 121). We prove that this is minimal, in the sense that if we use any smaller vector, then injectivity is lost (Theorem 128).
This technical report is formed from two conference papers [6, 5], and a journal paper [7]; the technical report includes all material, with full proofs.
2. Permissive nominal terms
Fix a countably infinite set of atoms. will range over distinct atoms (we call this the permutative convention). Fix a set of term-formers. f g h will range over distinct term-formers.
Call co-infinite when is infinite. Fix an infinite, co-infinite set comb .1 A permissions set has the form (comb) for finite sets and .
will range over permissions sets, whereas Permit is the set of all permissions sets.
Permit implies Permit, and and are infinite.
For each permission sort 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 5 onwards).
Define the domain of a function from atoms to atoms by:
A permutation is a bijection on atoms such that dom() is finite. and will range over permutations (not necessarily distinct).
Write id for the identity permutation such that id( always. Write () for the swapping permutation that swaps and in the term .
Define (permissive nominal) terms by:
We write for syntactic identity; when and denote identical terms.
Atoms represent variable symbols; term-formers functions; unknowns meta-variables; abstraction [] binding; and a meta-variable with a suspended substitution, like ‘[]’. For example, suppose term-formers app and lam: app() can represent ‘’ ( applied to ). app(lam([])) can represent ‘()’ (identity applied to ). lam([]) can represent ‘’ if comb, and ‘, where fv()’ if comb.
See Section 4 for comparison with ‘ordinary’ nominal terms [27].
Define a permutation action by:
If , define the pointwise action by:
Define free atoms fa() by:
Define fV () by:
Define -equivalence inductively by:
Here, denotes the partial function ‘ restricted to ’; similarly for .
is either true or false. Compare with the corresponding notion for nominal terms, which is subject to a freshness context (Definition 37).
Theorem 13 and Corollary 14 are properties that ‘ordinary syntax’ has, that nominal terms do not have, and that permissive nominal terms recover; we can always choose a fresh variable, and we can always -rename with it.
For any , there exist infinitely many such that fa
By induction on .
The case . There are infinitely many atoms not equal to , as required.
The case f(). Suppose are the distinct permissions sorts of fV () for 1 . By Definition 2, each permission sort differs finitely from, comb. Therefore, we have for every and , that differs finitely from combs, too. There exists infinitely many , for every , and . The result follows from the inductive hypotheses.
The case []. By inductive hypothesis, infinitely many fa() exist. There exists infinitely many fa
The case . By Definition 9, fa(. Infinitely many exist, by the co-infinite nature of , therefore infinitely many exist. The result follows.
For any and there exists infinitely many fresh (so fa) such that for some ,
Immediate, by Theorem 13 and (=[b]).
Our changes do not affect basic results about nominal terms [27]:
1. id
2. () ()
By induction on .
The cases and f(). These are straightforward.
The case []. We have:
The case . As id , we have id . Further:
fa( fa().
By induction on .
The case and f(). These are easy.
The case []. We have:
The case . We have:
fV ( fV
By induction on .
The case . Since fV ( fV (()), the result follows.
The case f(). We have:
The result follows.
The case []. We have:
The result follows.
The case . By Definition 7, () () . Then fV ( fV (() ), and the result follows.
If then .
By induction on .
The case (=a). Using (=a), (() always.
The case (=f). By hypothesis, for 1 . Extending with (=f), we have f( f(). This implies f( f(). The result follows.
The case (=[a]). By hypothesis, . We use (=[a]) to conclude [()]( [()](). The result follows.
The case (=[b]). Suppose () with fa By Lemma 15 and inductive hypothesis, (()) . By Lemma 16, () fa(). Further, ((
The case (=X). Suppose so that . Then () ()X), () () . The result follows.
If then fa( fa
By induction on .
The cases (=af) and (=[a]). Easy.
The case (=[b]). Suppose []
The case (=X). We have fa( and fa(. By assumption, , therefore . The result follows.
If then .
To prove Theorem 24, we introduce the following notion:
Define the size of a term by:
size( size()
By induction on .
The case . Since size(( size
The case f(). We have:
The case []. We have:
The case . By Definition 7, () (). Then, size( size(() ). The result follows.
For every term , the set size
As size
is transitive, reflexive, and symmetric.
We handle the three claims separately:
The reflexivity case. We prove by induction on .
The case . Straightforward, using (=a).
The cases f() and []. These are easy consequences of the inductive hypotheses.
The case . Note, . Using (=X), .
The symmetry case. We prove by induction on .
The cases (=a) and (=f). Easy.
The case (=[a]). Suppose so by hypothesis. Using (=[a]),
The case (=[b]). Suppose () with fa By Lemma 16, fa(() ). By Lemma 15, and as , () . By Lemma 19, fa(), and by hypothesis, () . Using (=[b]), []
The case (=X). Since equality on partial functions is symmetric.
The transitivity case. By Lemma 23, we may perform induction on the size of a term. We prove, given and , that by induction on size
The cases and f(). Easy.
The case []. We examine only the most complex case, where all abstracted variables are distinct. Suppose () and () with fa and fa(). By Lemma 18, () (() () . By Lemma 22, () (() , equivalent to () . By Lemma 19, fa(() ).
The case . Since equality on partial functions is transitive.
3. Substitutions
A substitution is a function from unknowns to terms such that fa(()) always. , , , , will range over substitutions.
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
Define a substitution action on terms by:
fa() fa
() ().
By induction on .
The case . We have:
The result follows.
The case f() and []. These are straightforward. The case .
The result follows.
fV ([]) fV
If for all fV , then .
By induction on .
The case . As fV (.
The case f(). Suppose for every fV () for 1 we have and by hypothesis. Using (=f), f( f(). By Definition 26, f() f(). The result follows.
The case []. Suppose, for every fa(), we have . By hypothesis, . Using (=[a]), []( [](). The result follows.
The case . By assumption, . By Lemma 18, ( (). By Lemma 28, () (). The result follows.
If then .
By induction on the derivation of .
The case (=aa). As .
The cases (=f) and (=[a]). These are immediate consequences of the inductive hypotheses.
The case (=[b]). Suppose () with fa(). Then (() ) by assumption. By Lemma 28, () . By Theorem 27, fa(). Using [b]), []( [](). By Definition 25, []() ([]). The result follows.
The case (=X). Suppose using (=X). Then and as fa(()) by assumption. The result follows.
Define composition by ()() (()).
()().
By induction on .
The cases , f() and []. Straightforward.
The case []. We have:
The result follows.
The case
The result follows.
4. Relation to nominal terms
Nominal terms are described fully elsewhere [27]. We inject ‘nominal’ into ‘permissive’. Main results are Theorems 41, 42, and 49.
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 dom) is finite. will range over permutations.
˙
Write for the inverse of , id for the identity permutation, and for function composition, as is standard. For example, ( ))
Define nominal terms with the following grammar:
Define a permutation action on nominal terms with the following rules:
Write for syntactic identity. f ranges over term-formers (Definition 1).
A freshness is a pair . A freshness context is a finite set of freshnesses of the form # . Define derivable freshness on nominal terms by the rules in Figure 1.
A equality is a pair . Define derivable equality on nominal terms by the rules in Figure 2.
Define a mapping from nominal permutations to permissive nominal permutations by ()) and ( for all other . Define an interpretation by:
Here, we make a fixed but arbitrary choice of for each , injectively so that and are always distinct.
commutes with permutation and it preserves and reflects freshness:
By induction on .
The case . Suppose and ((). Then (()) and (. The result follows.
The case .
The case [. We have:
The result follows.
The case f). This is routine.
) fa() if and only if .
We handle the two implications separately.
The case ) fa() implies ∆ . We proceed by induction on .
The cases and f). Straightforward.
The case [. There are two cases to consider:
The case [. Using (#[ȧ always.
The case [. Suppose ) fa([() and ) fa() (). Then ) fa(), therefore ∆ by hypothesis. Using (#[ḃ ]), #[. The result follows.
The case . Suppose ) fa( ). Then ) , where comb ) # . But comb ) # equivalent to comb ) # . Then ) # ) # . By Definition 38, and the fact permutations are bijective, ) #) #. Using (#Ẋ ), # . The result follows.
The case ∆ implies ) fa(). We proceed by induction on the derivation of ∆ .
The cases (# ḃ) and (#f). Routine.
The case (#[ȧ]). Suppose ∆ using (#[ȧ]). Then [)]. Further, ) fa() ). The result follows.
The case (#[ ḃ]). Suppose ∆ and ) fa) by assumption. Using (#[ ḃ#[. Then, fa([ fa() (). The result follows.
The case (# Ẋ). Suppose )# ∆, and ∆ using (#Ẋ ).
fa(. The result follows by Definition 38.
implies .
By induction on the derivation of .
The case . We have ). Using (=aa), and . Using ȧ. The result follows.
The case f). Suppose f)f). Then for 1 . By hypothesis, ∆ for 1 . Using f), ((). Then ( f). The result follows.
The case (=[a]). Suppose and ∆ . Using (=[a]), [)] [)]. Using (=[ȧ. Then [)]. The result follows.
The case (=[b]). Suppose (() )) and () fa(). By Lemmas 39 and 40, () and ∆ . By hypothesis, ∆ () . Using (=[ḃ . The result follows.
The case (=X). Suppose where comb) # . is injective, so # ∆for all such that ) ). The result follows.
If then .
By induction on the derivation of ∆ .
The case (=ȧ). Straightforward.
The case (=f). Routine, by the inductive hypotheses.
The case (=[ȧ]). Suppose ∆ and . Using (=[ȧ . Then, )] and )]. Using (=[a]), [)] [)] whenever . The result follows.
The case (=[ ḃ]). Suppose ∆ () and ∆ . By hypothesis and Lemma 39, () . By Lemma 40, () fa(). The result follows [b]).
The case (= Ẋ). Recall that and where comb ) # . Suppose ) ) implies ∆ # . By Lemma 40, ()) ()) implies ) . The result follows by (=X).
A substitution is a function from nominal unknowns to nominal ˙
terms such that ( ) id is finite. will range over nominal ˙ ˙
substitutions. Write id for the identity, mapping to id .
Define a substitution action on nominal terms by the following rules:
A unification problem is a finite multiset of freshnesses and equalities. A solution to is a pair (∆) such that ∆ for every , and ∆ for every . This follows [27, Definition 3.1]. We extend our interpretation to solutions by:
) .
By induction on .
The cases and f). Routine.
The case [. We have:
The result follows.
The case . We have:
The result follows.
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 () .
We handle the two implications separately.
The case fa() implies () . We proceed by induction on .
The case . Straightforward.
The case f(). Easy, by the inductive hypotheses.
The cases [] and []. We handle only the [] case, as the other is similar. We show ()
The case []. Suppose fa([]), fa([]) and fa(). We show ()
The case . Suppose fa(), fa() and . By Definition 7, () () (()) . Using (=X), (()) whenever (()). As , (()), and the result follows.
The case () implies fa We proceed by induction on .
The case , , and f(). These are routine.
The case f(). By hypotheses, () () implies fa
The cases [] and []. We handle only the [] case, as the other is similar. Suppose ()
The case []. By hypothesis, () implies fa(). Then []() ()
The case . Suppose () . By Definition 7, () (()). Using (=X), (()) whenever (). However, () only when . The result follows.
No solutions go missing, moving from the nominal to the permissive world:
) solves if and only if ) solves .
5. Support inclusion problems
Nominal unification has ‘freshness problems’; the algorithm of [27] solves these concurrently with equality problems. We prefer to factor the algorithm differently, so that problems to do with free atoms are solved separately from problems to do with equalities. The linkage is isolated in rule (I3) (Definition 75). Permissions sets differ finitely from comb or , so although we are manipulating infinite sets, we may represent them as finite data structures in any implementation.
5.1. Simplification reduction and normal forms
A support inclusion is a pair of a term and a permissions set. 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. Call Inc solvable when Sol(Inc) .
Define a simplification rewrite relation by:
If Inc then Sol(Inc Sol().
First, we make the following claims:
Claim 1: If then fa() always. As fa( fa(
Claim 2: fa(f()) if and only if fa() for 1 . As fa(f(
Claim 3: fa(([])) if and only if fa() . Suppose fa(([])) ,
result follows. The reverse direction is similar.
Claim 4: fa(()) if and only if fa() . We consider only one case.
fa() by assumption. By Lemma 16, fa() . By Lemmas 15 and 16, () fa() . As id, we have fa([]) . The result follows.
result follows. The reverse direction is similar.
Claim 5: If then fa() always. Note, if and only if and fa(. By Lemmas 28 and 16, fa(fa(()) . Then, fa() . The result follows.
We proceed by case analysis on Inc (Definition 51):
The case (a). Suppose . If Sol( ) then Sol() and the result follows. Otherwise, suppose Sol(). Using Claim 1, fa() . The result follows.
The case (f). From Claim 2.
The case ([]). If Sol( ) then fa() . By Claim 3, fa([]()) . As fa([]( fa(([])) and Sol(). The result follows. The reverse direction is similar.
The case (X). Suppose , id and Sol( Inc), so fa(()) . By Claim 4, fa() , and as Sol(). The result follows. The reverse direction is similar.
The case (). Suppose . If Sol( ) then Sol() and the result follows. Otherwise, suppose Sol(). By Claim 5, fa() . By Lemma 28, fa(()) . The result follows.
Define the size of a support inclusion problem size(Inc) to be a tuple (), where:
is the number of term formers appearing within terms in Inc,
is the number of abstractions appearing within terms in Inc,
is the number of permutations, distinct from the identity permutation, appearing within terms in Inc, and
is the number of support inclusions within Inc. Order tuples lexicographically.
Support inclusion problem simplication is strongly normalizing.
By case analysis on , showing that each rule reduces the measure (Definition 53).
The case . Suppose , size( ), and using (a). Then size( 1).
The case f() . Suppose size(f() ) and f() by (f). Then size( 1 1). The result follows from the ordering.
The case [] . Suppose size([] ) and [] using ([]). Then size( 1) and the result follows.
The case . Suppose size( ). Then, if , we have using (), with measure ( 1). Otherwise, if we have and id, we have with measure ( 1).
Support inclusion problem simplification is strongly confluent.
As an immediate corollary, support inclusion simplification is confluent.
We prove the result by induction on the cardinality of Inc.
The case Inc . As no rewrites are applicable.
The case Inc . Note for each only one simplification rule may be applied. The result then follows from the inductive hypothesis.
The corollary follows, as all strongly confluent rewrite relations are confluent (see [1] for details).
We conclude with a few useful observations:
Call Inc consistent when nf (Inc) for all atoms and permissions sets .
If Inc is consistent then all inc nf (Inc) have the form where .
By inspection.
5.2. Building solutions
Our main results are Theorems 62 and 70.
Define fV (Inc) by fV (IncfV
Recall from Definition 3 that ranges 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:
It is easy to verify that fa(()) always.
If Inc is consistent then Sol(Inc). (‘ solves Inc’.)
Suppose Inc -normal form. If Inc then ( id for an which satisfies . The result follows.
More generally, if Inc is not a =-normal form, by Theorem 52 Sol(Inc Sol(nf (Inc)), and we use the previous paragraph.
By Theorem 52 Sol(Inc Sol(nf (Inc)), so it suffices to show the result for the case when Inc -normal form.
Suppose Inc is inconsistent, so nf () contains a support inclusions of the form where . Then always, so there is no substitution such that . Conversely, if Inc is consistent, the result follows by Lemma 61.
Suppose that Inc is consistent, fV (Inc) , and Sol(Inc). Define a substitution by:
()() () if and () id .
()() () if .
We check that Definition 63 is well-defined:
If exists then it is well-defined.
Suppose exists. Then:
Suppose and . By Definition 63, ()() () and ()( ( The result follows, as substitutions are well-defined.
Suppose , () id , ( id and . Then ()() () and ()() ( Since the result follows as substitutions are well-defined.
Suppose () id , and . Then ( )( ( and ()() (). By Definition 60, () id as . The result follows as substitutions are well-defined.
The case , ( id , and is similar to the case for () id , and .
If Sol(Inc) then exists.
If exists, then it is well-defined.
Suppose exists and Then:
and . Then ( id and ( id . By Definition 60, and are chosen so . The result follows.
and . Then ( id and ( id The result follows.
and . Then ( id and ( id with . The result follows.
The case and is similar to the case for and .
If Inc then fV () fV (Inc).
By case analysis on the rules defining = (Definition 51).
The case (a). Suppose and using (a). By Definition 59, fV ( fV (). The result follows.
The case (f). Suppose f() using (f). By Definition 59, fV (f() fV ( ). The result follows.
The case ([]). Suppose [] using ([]). By Definition 59, fV ([] fV (). By Definition 10, fV ([] fV ( ). The result follows.
The case (X). Suppose , id and using (X). By Definition 10, fV ( fV (). By Definition 59, fV ( fV ( ). The result follows.
The case (). Suppose and using (). By Definition 59, fV () fV ( ). The result follows.
fV (nf (Inc)) fV (Inc)
By Lemma 67.
If Sol(Inc) and fV (Inc) then is a substitution.
By Lemma 65, exists. We show fa(()()) by cases:
The case id () for . By Corollary 68, fV (nf (Inc)) fV (Inc). Then fV (nf (Inc)) , as fV (Inc) by assumpyion. There are two sub-cases:
The case fV (nf (Inc)). Then and ()(() by Definition 63. By assumption, fa(()) . The result follows.
The case fV (nf (Inc)). By assumption, Sol(Inc) so Sol(nf (Inc)) by Theorem 52. by Definition 50, fa(()) for every such that nf (Inc). By Definition 63, nf (Inc). The result follows.
Otherwise, ()() () and fa(()) by assumption.
If Sol(Inc) and fV (Inc) then () (())() for every .
For some fresh , () id , and ()() (). The result follows by Lemma 15.
6. Permissive nominal unification problems
6.1. Problems, solutions, the unification algorithm
An equality 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 45 or [27, Definition 3.1]) based on ‘a substitution + a freshness context’. We can do this, because in permissive nominal terms, freshness information is fixed. Lemma 73 will be useful:
Sol() if and only if Sol().
If is a problem, define a support inclusion problem by:
Call a support inclusion problem Inc non-trivial when nf (Inc) .
In (I3) we insist that is non-trivial to avoid indefinite rewrites. We insist is consistent so that exists. and are defined in Definition 60.
If ; ; by a non-instantiating rule then Sol( Sol().
As the empty set cannot be simplified, it must be the case that . It suffices to perform case analysis on the simplification of . We assume, without loss of generality, that has been simplified by non-instantiating rules as much as possible.
The cases (a), (f) and (X). Straightforward.
The case ([a]). Suppose ]
Suppose ([]) ([]). By Definition 26, []( [](). By the rules in Definition 11, . The result follows.
Suppose . By the rules in Definition 26, []( [](). By Definition 26, ([]) ([]). The result follows.
The case ([b]). Suppose ]
Suppose ([]) ([]). By Definition 26, []( [](). By the rules in Definition 11, ()(. By Lemma 28 and Theorem 24, (()). The result follows.
Suppose (() ). By Lemma 28 and Theorem 24, () (. By Theorem 27, fa(). Using (=[b]), []( [](). By Definition 26 []( [](). The result follows.
Define 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 75 as much as possible.
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.
Suppose (() for all fV (). Then Sol() if and only if Sol().
Write for the substitution such that:
()() id and ()( ( for all other
Suppose and fV . Then
We reason as follows:
6.2. Simplification rewrites calculate principal solutions
Write when there exists some such that () always. 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 88 — the unification algorithm from Definition 79 calculates a solution — and 93 — the solution it calculates, is principal.
If fV () and ; ; using a non-instantiating rule, then fV () .
As the empty set cannot be simplified, it must be that . Therefore, we perform case analysis on the simplification of .
The cases (a), (f) and (=X). Routine.
The case ([a]). Suppose ; []
The case ([b]). Suppose ; [] , fa() with fV ([]
By Definitions 10 and 77 and Lemma 17, fV (() ) . The result follows.
If fV () and ; ; using an instantiating rule, then fV () .
If then ([])]()
There are multiple cases to consider:
The case with . We have:
The case with . We have:
The case with . Since ([])( id and id
Recall that is defined in Definition 78:
If fV () then ; ; implies Sol().
By induction on the length of the path in .
Length 0. Then and id. The result follows.
Length . There are three cases:
The non-instantiating case. Suppose ; ; ; . By Lemma 85, fV () . By inductive hypothesis, Sol(). By Lemma 76, Sol(). The result follows.
The case of (I1) or (I2). Suppose ; ; ; . By Lemma 86, fV () . By inductive hypothesis, Sol(). By Lemma 87, ()(). By Lemma 73, () Sol(). The result follows.
The case of (I3). Suppose ; ; ; . By Lemma 86, fV () . By inductive hypothesis, Sol(). By Lemma 73, () Sol(). By Lemma 87, (). By Lemma 80, () Sol(). The result follows.
We need some lemmas for Theorem 93:
If then .
Suppose always. Then implies .
If then ().
There are multiple cases to consider:
The case . Then ()( id and ()( id . The result follows.
The case with . Then ()( id and ()( id The result follows.
The case with . Then ()(( and ()( ( As (( when . The result follows.
Suppose fV () . If ; ; then is a principal solution to (Definition 84).
By Theorem 88, Sol(). We prove is principal by induction on the path length of ; ; .
Length 0. So and id. By Definition 83, id.
Length . We consider the rules in Definition 75.
The non-instantiating case. Suppose
where ; ; is a non-instantiating simplification rewrite. By inductive hypothesis, is a principal solution of . By Lemma 76, is a principal solution of . The result follows.
The case (I1). Suppose fa
Further, suppose that Sol().
By inductive hypothesis, (). By Lemma 89, () (). By Lemma 87, (). By Lemma 92, () . By Theorem 82 and Lemma 90, () 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 suppose that Sol(). By Theorem 88, Sol(). It is a fact that , so fV () . By Lemma 91, Sol(). By Theorem 70 and Lemma 80, () Sol(). By Lemma 73, Sol(). By inductive hypothesis, . By Lemma 89, (). It is a fact that (). By Theorem 70 and Lemma 90, () as required.
Given a problem , if the algorithm of Definition 79 succeeds then it returns a principal solution; if it fails then there is no solution.
If the algorithm succeeds we use Theorem 93. Otherwise, the algorithm generates an element of the form f() f() where , f() g(), f()
7. The -calculus
Let range over distinct unknowns.
Define -terms by:
Here f ranges over term-formers, and ranges over atoms (see Definition 1). will range over -terms.
Define a permutation action by:
Write for the composition of permutations and , and id for the identity permutation on -terms.
Define free atoms by:
Let -equivalence = be the least relation on -terms such that:
It is not hard to prove that Definition 98 does indeed specify the usual -equivalence relation on -terms. Our definition is designed to match the definition of -equivalence on nominal terms (Definition 11). This makes later results easier to prove (for example Theorem 126).
Lemma 99 to Theorem 107 mirror similar results for permissive nominal terms.
If then .
By induction on .
The cases , f and . Routine.
The case . We wish to show . There are two cases to consider:
The case ( By inductive hypothesis.
The case () We wish to show . Using (a), this is equivalent to showing (
The case . Routine.
() ()
By induction on .
The case . We have:
The cases , f and . These are routine.
The case . We have:
The result follows.
fa( fa
By induction on .
The case . We have:
The case and f. These are straightforward.
The case . We have:
The result follows.
The case . We have:
The result follows.
implies .
By induction on the derivation of .
The case (a). Using (a), (
The case (X) and (f). Routine.
The case (p). By inductive hypothesis, and . Using (p), ()( ()(). By Definition 96, ()() . The result follows.
The case (aa). By inductive hypothesis, . Using (aa), ((). By Definition 96, . The result follows.
The case (ab). By inductive hypothesis, ((). By Lemma 100, (()) (()). It is a fact that (
If then fa( fa
By induction on the derivation of .
The cases (a), (X) and (f). Straightforward.
The case (p). By inductive hypothesis, fa( fa() and fa( fa(). As fa( fa
The case (aa). By inductive hypothesis, fa( fa(), hence fa
The case (ab). Suppose using (ab), with fa(). We aim to show fa( fa(), that is, fa
Define a notion of size on -terms by:
For every lambda-term , the set size
Since the set size
size( size()
By induction on .
The cases , and f. Straightforward.
The case . We have:
The result follows.
The case . We have:
The result follows.
is transitive, reflexive, and symmetric.
We handle the three cases separately.
The reflexivity case, . We proceed by induction on .
The case , and f. Routine.
The case . By hypothesis, and . Using (p), . The result follows.
The case . By hypothesis, . Using (aa), . The result follows.
The symmetry case, implies . We proceed by induction on the derivation of .
The cases (a), (X) and (f). Routine.
The case (p). By inductive hypotheses, and . Using (p), . The result follows.
The case (aa). By inductive hypothesis, . Using (aa), . The result follows.
The case (ab). Suppose () with fa(). By inductive hypothesis, (). By Lemma 103, fa(). By Lemma 102, () ()(()). By Lemma 100, () (()()), therefore ().
follows.
The transitivity case, and imply . Following Lemma 105, we proceed by induction on size
The cases , and f. Straightforward.
The case . By the inductive hypotheses.
The case . There are multiple cases to consider. We consider the most difficult, the case where all abstractions are named apart. Suppose and . We aim to show .
fa(). Using (ab), the result follows.
Let -equivalence = be the least relation such that ()[] and closed under the rules of Definition 98.
Call a function from unknowns to -terms a (-calculus) substitution. will range over substitutions (and later so will ; Definition 142).
Define the capture-avoiding substitution action on -terms by:
In the final clause, ‘ fresh’ denotes a fixed but arbitrary choice of such that fa() fa
( ()
By induction on size
The cases , f and . Straightforward.
The case . We have:
The result follows.
The case with () fa(rng()). We have:
The result follows.
The case with fa(rng()) or
The result follows.
Definition 112 is an analogue of the substitution action on permissive nominal terms from Definition 32:
Define composition by: ()() (()).
()
By induction on size
The case . Since .
The case . By Definition 112.
The case f. Since f f and f f.
The case . We have:
The result follows.
The case with fa(rng()) fa(rng()). We have:
The result follows.
We define unification problems as usual and write ‘’ for an equality considered as part of a unification problem. solves a problem when for every in the problem, as usual.
We conclude with definions of pattern and pattern substitution [22, 21]. Recall that, unlike [19], we work in an untyped -calculus.
Let map each unknown to a natural number which we call its arity. Define -patterns, a subset of -terms, by:
Call a pattern when it is a -pattern for some . will range over patterns.
Call a -pattern substitution when every () is a -pattern. Call a pattern substitution when is a -pattern substitution for some .
So is a pattern when every in occurs as , for some
8. Translating nominal terms into the -calculus
8.1. The translation -, and its soundness
Call a finite list of distinct atoms a vector. range over vectors. Write [] for the vector containing , . . . , in that order.
Suppose . Write for the vector of atoms in that occur in , in order; thus [] ]. Write when every atom in is in . Write when every atom in is in .
Translate a nominal term to a -term by:
By induction on .
The case . We have:
The result follows.
The case f(). We have:
The result follows.
The case []. We have:
The result follows.
The case .
The result follows.
Lemma 119 is useful for the proof of Theorem 120:
fa() fa
By induction on .
The cases and f(). Routine.
The case f(). We have:
The result follows.
The case []. We have:
The result follows.
The case . We have:
The result follows.
If then
By induction on the size of . We reason by cases on the last rule in the derivation of :
The cases (=af) and (=[]aa). Straightforward.
The case (=X). There are two cases to consider:
The case Then . Using (X), the result follows.
The case ] and 1. By assumption, .
Using (p), (X), and (a), the result follows.
The case (=[]ab). By assumption, () and fa(). Choose fresh , so fafa(). By Lemma 18, () (). By inductive hypothesis, () (). Using (aa), () (). By Lemma 118, (()
8.2. Capturable atoms; injectivity and minimality
The main results of this subsection are Theorems 126 and 128, and also Definition 121.
(Definition 117) is parameterised by a vector . Levy and Villaret introduced a similar translation [19, Definition 2]; they used all the atoms in . We now show that the smaller set of capturable atoms in (Definition 121) is consistent with injectivity of the translation (Theorem 126), and that it is minimal (Theorem 128).
Define the capturable atoms of a term (with respect to a set of atoms) () inductively by:
Write capt() as capt
For instance, if comb ) , then capt([][] and capt(()
If fa then (
By induction on .
The case . Routine.
The case f(). If fa(f()), then by Definition 9, fa() for 1 . We have:
The result follows.
The case []. If fa([]), then by Definition 9, fa(). We have:
The result follows.
The case . If fa(), then . By Definition 121, ( (dom
If dom
By induction on .
The cases and f(). Straightforward.
The case . Since (( ().
The case f(). We have:
The result follows.
The case []. We have:
There are two cases to consider:
The case (. Then:
The result follows.
The case () . Then:
The result follows.
The case . We have:
The result follows.
If fa then ([] ([]() ).
We have:
The result follows.
If then ( ().
By induction on the derivation of .
The case (=aa). Straightforward.
The case (=f). Suppose . By hypothesis, ( ( . Using (=f), f( f(). Then, (f( () (). The result follows.
The case of (=[a]). Suppose . By Definition 121, ([] similarly for . By inductive hypothesis, ( (). The result follows.
The case of (=[b]). Suppose fa(), () , and []() . The result follows by Corollary 124.
The case of (=X). Suppose . Then, dom
Let be a vector. Let and be nominal terms and let be finite. Suppose () () . Then
As a corollary, if captcapt
For the first part, we work by induction on the size of , reasoning by cases on the last rule in the derivation of
The cases (a) and (aa). Routine.
The case (ab). Suppose ()
hypothesis, () () . Using (=[]ab), and by Theorem 107, []
The case (app). By Definition 117, there are two cases:
The case f and f and
The case
The case (X). From the form of the translation, and and dom
The corollary follows from the first part and Lemma 125.
() implies fV exists such that .
By induction on .
The cases and . Since (.
The case f(). Suppose (f()), with () for some with 1 . By hypothesis, fV () with . Then fV (f( fV
The cases [] and []. We handle the first case, the second is similar. Suppose ([]). Then (). By hypothesis, fV exists with . As fV ([] fV (), the result follows.
The . By Definition 121.
If capt() then there exists some such that and
Suppose capt() and . By Lemma 127, fV () exists with . Choose fresh , so fa
9. Translating substitutions; relating solutions of nominal and pattern unification problems
9.1. Translating substitutions
The main result of this subsection is Theorem 131.
We extend the translation to substitutions, to then prove that if a substitution solves a nominal unification problem, then its translation solves the translation of the problem. This raises a difficulty: may solve but in substituting it may introduce new capturable atoms (consider ]] solving , where ). This motivates introducing another vector , to account for the capturable atoms ‘after’ the substitution. Accordingly, we will introduce another vector that contains at least the capturable atoms of .
Define by:
Lemma 130 is useful in the proof of Theorem 131:
dom
By induction on .
The case . Suppose ( so , therefore [] for 1 , as required. Otherwise, suppose () , so . Then [] () for some 1 . The result follows.
The case , f and . Routine.
The case . Suppose (, so therefore (). Write for ()
The result follows. Otherwise, suppose () so and therefore
The result follows.
If capt
By induction on .
The cases . Routine.
The case f(). We have:
The result follows.
The case . Let be . By Definition 129, ( (). Then:
The use of Lemma 130 above is valid, as capt() , therefore dom by Definition 121. The result follows.
The case []. Choose fresh, so fa(()) for every fV () and fa(). Then:
The result follows.
Recall the instantiation ordering from Definition 83. Similarly:
Write when there exists some such that (), for any . Call the instantiation ordering.
We can leverage Theorem 131 to prove a corollary, describing a sense in which the instantiation ordering of Definition 83 translates to the instantiation ordering of Definition 132:
Suppose capt(()) .
Suppose . By Definition 83, there exists such that () always. We reason as follows, for any unknown :
The result follows.
In Corollary 133, the precondition capt(()) is necessary to prevent from introducing infinitely many capturable atoms. The ‘complexity’ of is unconstrained. In practice it is likely that we will care about a particular finite set of unknowns (for example, fV () for some ), and the precondition can be correspondingly refined to consider just .
9.2. Reducing permissive nominal unification to pattern unification; soundness, weak
completeness The main result of this subsection is Theorem 141. It says that if and are ‘large enough’, then solves if and only if solves .
An equation is a pair . A unification problem is a finite set of equations. A solution to is a such that for all .
If ] and then define by:
If then () ().
As a corollary, () ([]).
By induction on .
The case . As (.
The case f(). We have:
The result follows.
The case []. We have:
The result follows.
The case . We have:
The result follows. As ([] (), the corollary follows.
We need Lemma 137 to prove Lemma 138:
() ((dom
fa
The first part is by induction on .
The cases and f(). Straightforward.
The case []. Then:
The result follows.
The case . As ()[] , we reason as follows:
The result follows. The second part follows from the first.
capt() capt(()) is not true in general. For example if and then capt([]
Suppose capt() and capt() . Then solves if and only if solves .
Suppose capt() , and capt(()) , with . Then solves if and only if solves .
The solution [f()] with comb translates to the solution [(f () )()].
9.3. Strong Completeness
The main result of this subsection is Theorem 155. This strengthens the completeness result of Theorem 141, in a certain sense, by expressing that a class of solving all originate from solving , in a suitable formal sense.
fa( fa()
By induction on .
The case . Since .
The case . Since fa( and is a bijection on unknowns.
The case f. Since f f.
The case . By hypothesis, fa( fa() and fa( fa(). As fa( fa
The case . As fa(() fa(()) we have fa(( fa() . By hypothesis, fa( fa(). The result follows.
if and only if .
The left to right implication is by induction on the derivation of ; right to left is by induction on the derivation of .
The cases (aa), (X) and (f). Routine.
The cases (p) and (aa). By the inductive hypotheses.
The case (ab). For the left to right implication, by hypothesis, (()) with fa By Theorem 107 and Lemma 111, () . By Lemma 143, fa(). Using (ab), ((). The result follows. For the right to left implication, suppose (() ) with fa(). By Theorem 107 and Lemma 111, () . By Lemma 143, fa(). Using (ab), . The result follows.
Define the substitution by: ()()
Note that is a substitution. () is not a shorthand for (), and the two are not equal in general.
If dom
By induction on size
The case . By assumption, and .
The case . Since () () by Definition 145.
The case f. Since f f and f f.
The case . If dom
The case . There are multiple cases to consider:
The case fa(), fa() and (. Then:
The result follows.
The case fa(), fa() and () . Pick fresh , so fa fa(), fa() and () . Every permutation has finite support, so is guaranteed to exist. Then:
The result follows. All other cases are similar to the case for fa(), fa() and () . The result follows.
solves if and only if does.
Suppose dom
For the first part, we have two cases:
The case solves implies solves . Suppose and solves . Then . By Lemma 144, . By Lemma 113, ((). The result follows.
The case solves implies solves . Suppose and solves . Then ((). By Lemma 113, . By Lemma 144, . The result follows.
For the second part, suppose dom
Lemma 147 expresses an intuition that ‘names of atoms and unknowns on the right in a solution, do not matter’, which also underlies the and in Theorem 155. is the price we pay for using the same unknowns in Definitions 95 and 6: This design decision makes Definition 117 compact, but it causes technical problems in Lemma 154, because () can introduce new unknowns over whose permission sorts (back in the nominal world) we have no control. lets us rename those new unknowns as convenient. As for , we discuss it below.
Another design decision is to work with an untyped -calculus. This simplifies our presentation and makes our results slightly more powerful (because they apply to more substitutions), but we cannot be too liberal: Suppose solves . Examining Definition 117, if occurs in then it is applied to a number of atoms equal to the length of . So, we will only be interested in that respect this fragment of typability ( will be fV ()):
Let be a finite set of unknowns. Call -consistent on when for every , ( where is the length of . (So () starts with ‘at least’ length--many -abstractions.)
Call strictly -consistent when also, for every , fa(())
Strictness is motivated by the following examples: Take ].
Take f([]) with comb. Then the problem () (f (()) ()) has the solution (f () ) ]. ()(
Take f([] with comb and comb . Then () (f ( has the solution (f () ) ]. ()( ( is impossible, since fa() whereas fa(() by Lemma 119.
The in ( for the two considered above, has nothing to do with the in . We can regard this as an unfortunate ‘name-clash’ which Lemma 147 allows us to eliminate with a permutation .
More on this in Theorem 155. We continue with the proofs:
Define the arguments of unknowns in a pattern by:
does not imply args( args(). This is by design.
Suppose is a -pattern and args
Here is a fixed but arbitrary choice of permutation of the atoms in , mapping the element of (Definition 116) to for 1
args
By induction on .
The cases and f. Routine.
The case . Suppose args() so that args
The case . Then and
Suppose is a finite set of unknowns and is a -pattern substitution, strictly -consistent on .
()(
Take any ] which includes all atoms in and in
By assumption ( for a -pattern , where [. Take
We can verify that capt(()) . We then reason as follows:
Suppose capt() .
For strictly -consistent on fV () solving there are , , and , such that ()(
For -consistent on fV () solving there are , , , and , such that ()(
By Lemma 154, there are , , and , such that ()(
For the second part, write ], choose ] fresh (so is not in , , or () for any fV ()), and take ) (). is strictly -consistent and the result follows from the first part and Lemma 147.
10. Conclusions
Nominal contrasted with permissive nominal terms. Permissive nominal terms come closer to first- and higher-order terms than nominal terms do, but they are a special case of neither. The idea of associating permissions sets to unknowns is mentioned already in [27, Remark 2.6]. What really makes that idea come alive, in this paper, is the use of fixed permissions sets of co-infinite sets of atoms. This has beneficial technical repercussions which go well beyond ‘just tweaking nominal terms’. We recover Theorem 13 and Corollary 14, -equivalence is a property of terms (of course; there are no longer freshness contexts) — and the notions of unification problem and solution are based on equality (rather than equality-and-freshness-context) with no loss of expressivity.
Permissive nominal terms do not obsolete nominal terms; if we want to talk about ‘an arbitrary term’, then a nominal terms unknown is more directly useful than a permissive nominal terms unknown (which means ‘an arbitrary term, mentioning atoms in comb’).
In Section 4 we connected the ‘permissive’ and the ‘nominal’ worlds in some technical detail. In nominal terms, if we need a fresh name then we can enrich the freshness context (consider [12, Figure 2, axiom (fr) ] and [13, e.g. Lemma 25 and Theorem 33]). One nice way to view the interpretation of Section 4 is that comb plays the rôle of ‘the atoms we had so far’ and comb that of ‘the atoms we will generate fresh in the future’.
Related work on unification. Patterns emerged by studying Skolemisation of unification problems [22]; they proved useful in the unification of higher-order abstract syntax terms [21]. Cheney proposed a two-stage translation of higher-order to nominal unification [3], first by exhibiting a translation of higher-order pattern unification to nominal pattern unification (where nominal patterns are a variant of nominal terms, with a concretion operator, where unknowns have empty support), followed by a translation between nominal pattern unification and nominal unification. Levy and Villaret’s translation [19], of nominal unification to higher-order patterns, crystallised an intuition that pattern unification is exactly what is needed to unify encodings of nominal terms. Their encoding is not minimal and addresses unifiability rather than individual solutions. In Section 8 we refined their encoding, using capt() (Definition 121) to obtain one that is minimal, and in Section 9 we established a precise sense in which solutions correspond across the translations.
Hamana’s unification of -terms with holes adds a capturing substitution [16]. 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 permissions sorts also describe which level 1 variable symbols (we call them atoms in this paper) may appear in them, though with our permissions sorts there are infinitely many that may, and infinitely many that may not. Another significant difference is that the treatment of -equivalence in Hamana’s system is not nominal (not based on permutations) and unlike our systems, Hamana’s does not have most general unifiers. Similarly, Qu-Prolog [23] adds level 2 variables, but does not manage -conversion in nominal style, and, for better or for worse, the system is more ambitious in what it expresses, and thus loses mathematical properties (unification is semi-decidable, most general unifiers need not exist).
Future work. We noted, in Definition 2, that comb is incompatible with the finite-support property of nominal sets [15, Definition 3.1]. This matters because permissive nominal terms can be directly quotiented by -equivalence, so it could be useful to apply the Gabbay-Pitts model of abstract syntax up to -equivalence [14]. We hypothesise that this can be overcome by using generalisations of nominal sets by the second author [10] or by Cheney ([2, Section 3], or [4]). We also hypothesise a theory of rewriting could be developed similarly to [9].
Via the interpretation in Section 4 this extends to solutions of ‘ordinary’ nominal unficiation problems. We have begun to apply permissive nominal terms to construct novel logics and -calculi, taking advantage of their properties to simplify the theory — we find it very useful to reason on terms (without a freshness context), to have an inexhaustible supply of fresh names, and to be able to quotient by -equivalence.
Nominal terms come with a denotation in nominal sets [14]. These are based on the idea of giving names a denotational reality as urelemente [28] (the atoms in this paper can be considered urelemente of a sets universe; this is a reason that nominal terms retain a first-order flavour). Famously, nominal sets exclude sets like permission sorts , because they do not have finite support. This is fully consistent with our use of permission sorts here; in this paper we are working at the meta-level where we can talk about any sets of atoms that we like. However, generalisations of nominal sets exist [10, 2] and we believe that permissive nominal terms can use them for denotation. Checking this is future work.
References
[1] Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, Great Britain, 1998.
[2] James Cheney. Nominal Logic Programming. PhD thesis, Cornell University, August 2004.
[3] James Cheney. Relating nominal and higher-order pattern unification. In Proceedings of the 19th International Workshop on Unification (UNIF 2005), pages 104–119, 2005.
[4] James Cheney. Completeness and Herbrand theorems for nominal logic. Journal of Symbolic Logic, 71:299–320, 2006.
[5] Gilles Dowek and Murdoch J. Gabbay. Relating the solutions of nominal unification and pattern unification. 2009. Available online at http://www.gabbay.org.uk/papers/relsnp.pdf.
[6] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive nominal terms and their unification. 2009. Available online at http://www.gabbay.org.uk/papers/perntu.pdf.
[7] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive nominal terms and their unification. 2009. Available online at http://www.gabbay.org.uk/papers/perntu-jv.pdf.
[8] 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.
[9] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, 2007.
[10] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205(7):982–1011, July 2007.
[11] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus. Electronic Notes in Theoretical Computer Science, 196:19–35, 2008.
[12] 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.
[13] Murdoch J. Gabbay and Dominic P. Mulligan. Two-and-a-halfth Order Lambda-calculus. Electronic Notes in Theoretical Computer Science, 2009. To appear.
[14] 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.
[15] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax Involving Binders. In 14th Annual Symposium on Logic in Computer Science, pages 214–224. IEEE Computer Society Press, 1999.
[16] 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.
[17] 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.
[18] J.-W. Klop, V. van Oostrom, and F. van Raamsdonk. Combinatory reduction systems. Theoretical Computer Science, 121:279–308, 1993.
[19] 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. Springer, 2008.
[20] Richard Mayr and Tobias Nipkow. Higher-order rewrite systems and their confluence. Theoretical Computer Science, 192:3–29, 1998.
[21] Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation, 1(4):497 – 536, 1991.
[22] Dale Miller. Unification under a mixed prefix. Journal of Symbolic Computation, 14(4):321–358, 1992.
[23] Peter Nickolas and Peter J. Robinson. The Qu-Prolog unification algorithm: formalisation and correctness. Theoretical Computer Science, 169(1):81–112, 1996.
[24] Lawrence C. Paulson. Isabelle: the next 700 theorem provers. In P. Odifreddi, editor, Logic and Computer Science, pages 361–386. Academic Press, 1990.
[25] F. Pfenning and C. Elliot. Higher-order abstract syntax. In PLDI (Programming Language design and Implementation), pages 199–208. ACM Press, 1988.
[26] 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.
[27] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, 2004.
[28] Ernst Zermelo. Untersuchungen über die Grundlagen der Mengenlehre. Mathematische Annalen, 65:261–281, 1908.
Notes
1The second author helped develop nominal sets [14], which famously disallow sets like comb (comb lacks finite support) [14]. Here, we are working at the meta-level, where we can talk about any subset or function that we wish. ↩
2‘fa(()) ’ looks absent in nominal terms theory ([27, Definition 2.13], [9, Definition 4]), yet it is there: see the conditions ‘()’ in Lemma 2.14, and ‘#()’ in Definition 3.1 of [27]. More on this in Section 4. ↩
3Note to referees: an error in a previous version of this paper, which made the algorithm incomplete, has been corrected. ↩
4We overload , for technical convenience: is partial and is total. ↩