HTML reading edition · 15 source pages · Open the source PDF

Permissive nominal terms and their unification

Gilles Dowek Murdoch J. Gabbay Dominic Mulligan

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 {x | φ(x)}. 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 y ∉ fv(t) then λx.t is α-equivalent with λy.[y/x]t” and

“How can we choose t and u to make λx.λy.(y t) equal to λx.λx.(x u)?”.

(We write fv(t) for the free variables of t; e.g. fv(λx.(xy)) = {y}.)

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 b#X ⊢ [a]X = [b](b a) · X. Here a and b denote atoms, which represent the ‘x’ and ‘y’; X denotes an unknown, it represents the ‘t’; b#X is a freshness side-condition, it represents the ‘y ∉ fv(t)’; (b a) is a permutation meaning ‘map a to b and b to a’, it represents the ‘[y/x]’ (we assumed y ∉ fv(t), 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 X in the empty freshness context, there is — by definition of the empty freshness context — no a such that a#X.1

We propose permissive nominal terms. An unknown takes the form XS where S is a permission sort (Definition 3). Permission sorts are sets of atoms that are both infinite and co-infinite (see Definition 2; S ⊆X is co-finite when X \ S 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 a, b ∈ comb. Assume a binary term-former (function-symbol) for application. Then:

−α-equivalence is ‘if y ∉ fv(u) then λx.u = λy.(u[x/x])’. In nominal terms this becomes b#Z ⊢ [a]Z = [b](b a)·Z.2 In permissive nominal terms it becomes [a]Zcomb\{b} = [b](b a) · Zcomb\{b}.

It is not possible to α-convert a in the nominal term ∅⊢ [a]Z; to do this, we must enrich the freshness context ∅.

In permissive nominal terms, it is always possible to α-convert a in [a]Zcomb\{b}; we can convert to any of the atoms not in comb \ {b}.

− ‘Unify λx.λy.(yt) with λx.λx.(xu)’ becomes in nominal terms ‘[a][b](bX) ?= [a][a](a Y)’ and has solution (b#Y, [X:=(b a) · Z, Y :=Z]).

In permissive nominal terms it becomes ‘[a][b](bXcomb) ?= [a][a](aY comb)’ and has solution [Xcomb:=Zcomb\{b}, Y comb:=Zcomb\{b}].

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

Definition 1

Fix a countably infinite set A of atoms. We use a permutative convention that a, b, c, . . . 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.

Definition 2

Call S ⊆A co-infinite when A \ S is infinite. Fix an infinite, co-infinite set comb ⊆A. A permission sort has the form (comb∪A1)\A2 for finite sets A1⊆A and A2⊆A. S, S′, T will range over permission sorts.

If S and T are permission sorts, so are S ∪T and S ∩T, and both S and A \ S are infinite.

Definition 3

For each S fix a disjoint countably infinite set of unknowns of sort S. XS, Y S, ZS, will range over distinct unknowns of sort S. If S ≠ S′ then there is no particular connection between XS and XS′. V will range over finite sets of unknowns (we use this from Section 4 onwards).

Definition 4

A permutation is a bijection on atoms such that {a | π(a) ≠ a} is finite. π and π′ will range over permutations (not necessarily distinct).

Write id for the identity permutation such that id(a) = a always. Write (a b) for the swapping which maps a to b, b to a, and all other c to themselves.

Definition 5

Define (permissive nominal) terms by:

r, s, t, . . . ::= a | f(r1, . . . , rn) | [a]r | π · XS

We write ≡ for syntactic identity; r ≡s when r and s denote identical terms.

Definition 6

Define a permutation action by:

π·a≡π(a) π·(f(r1, . . . , rn))≡f(π·r1, . . . , π·rn) π·[a]r≡[π(a)](π·r) π·(π′·XS)≡(π◦π′)·XS
Definition 7

If S ⊆A, define the pointwise action by: π · S = {π(a) | a ∈S}. Define free atoms fa(r) and unknowns fV (r) by:

fa(a)={a} fa(f(r1, . . . , rn)) = fa(r1) ∪. . . ∪fa(rn) fa([a]r)=fa(r)\{a} fa(π·XS)=π·SfV (a)=∅ fV (f(r1, . . . , rn)) = fV (r1) ∪. . . ∪fV (rn) fV ([a]r)=fV (r) fV (π·XS)={XS}

An intuition for fa(r) is ‘possible free atoms after instantiation’.

Definition 8

Let π|S denote the partial function ‘π restricted to S’. Define α-equivalence =α inductively by:

(=αaa)a =α ar1 =α s1· · · rn =α sn(=αf)f(r1, . . . , rn) =α f(s1, . . . , sn)r =α s(=α[a])[a]r =α [a]s(b a) · r =α s (b ∉fa(r)) (=α[b]) [a]r =α [b]s(π|S = π′|S)(=αX)π · XS =α π′ · XS
Lemma 9

id · r ≡r and π′ · (π · r) ≡ (π′◦π) · r.

Lemma 10

π · fa(r) = fa(π · r).

Theorem 11

=α is transitive, reflexive, and symmetric.

Lemma 12

For any r, there exist infinitely many b such that b ∉ fa(r). As a corollary, for any r and a there exists infinitely many fresh b (so b ∉ fa(r)) such that for some s, [a]r =α [b]s.

Proof

The first part is by an easy induction on r. We consider only the case r ≡π · XS: fa(π · XS) = π · S, and infinitely many b are such that b ∉π · S. The corollary follows using (=α[b]).

3 Substitutions

Definition 13

A substitution θ is a function from unknowns to terms such that fa(θ(XS)) ⊆S always (so S in XS describes the ‘permission’ we have to instantiate XS, namely to terms with free atoms in S). θ, θ′, θ1, θ2, will range over substitutions.3

Write id for the identity substitution mapping XS to id ·XS always. It will always be clear whether id means the identity substitution or permutation.

Suppose fa(t) ⊆S. Write [XS:=t] for the substitution such that [XS:=t](XS) ≡ t and [XS:=t](Y T) ≡ id · Y T for all other Y T.

Definition 14

Define a substitution action of substitutions on terms by:

aθ≡a f(r1, . . . , rn)θ≡f(r1θ, . . . , rnθ) ([a]r)θ≡[a](rθ) (π·XS)θ≡π·θ(XS)
Theorem 15

fa(rθ) ⊆ fa(r).

Proof

By induction on r. We consider the case r ≡π · XS. By definition fa(π · XS) = π · S. By assumption in Definition 13, fa(θ(XS)) ⊆S. Using Lemma 10, it follows that fa(π · θ(XS)) ⊆π · S.

Lemma 16

π · (rθ) ≡ (π · r)θ.

Proof

By a routine induction on r using the definitions and Lemma 9.

Theorem 17

If θ(XS) =α θ′(XS) for all XS ∈ fV (r), then rθ =α rθ′.

Definition 18

Define composition θ◦θ′ by (θ◦θ′)(XS) ≡ (θ(XS))θ′.

Theorem 19

(rθ)θ′ ≡r(θ◦θ′).

Proof

By induction on r. We consider the case of π · XS, and use Lemma 16: (π · XS)(θ◦θ′) ≡π · (θ◦θ′)(XS) ≡π · (θ(XS)θ′) ≡ (π · θ(XS))θ′ ≡ ((π · XS)θ)θ′

4 Support inclusion problems

Recall from Definition 13 that fa(θ(XS)) ⊆ fa(XS) = S, 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(rθ) ⊆T true” (Definition 27 and Lemma 25). In fact the algorithm calculates solutions that are most general, in a sense made formal in Theorem 32.

Definition 20

A support inclusion is a pair r ⊑T 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(rθ) ⊆T for every r ⊑T ∈ Inc. Write Sol(Inc) for the solutions of Inc.

Definition 21

Define a simplification rewrite relation by:

(⊑a) a ⊑T, Inc =⇒Inc (a ∈T)(⊑f) f(r1, . . . , rn) ⊑T, Inc =⇒r1 ⊑T, . . . , rn ⊑T, Inc(⊑[]) [a]r ⊑T, Inc =⇒r ⊑T ∪{a}, Inc(⊑X) π · XS ⊑T, Inc =⇒id · XS ⊑π-1 · T, Inc (S ⊈π-1 · T, π ≠ id)(⊑X′) π · XS ⊑T, Inc =⇒Inc (S ⊆π-1 · T)
Lemma 22

If Inc =⇒ Inc′ then Sol(Inc) = Sol(Inc′).

Proof

We consider (⊑X). Suppose S ⊈π-1 · T and π ≠ id. Suppose θ ∈ Sol(π · XS ⊑T, Inc). Then fa((π · XS)θ) ⊆T. By Lemma 16 (π · XS)θ ≡π · (XSθ). By Lemma 10 fa(π · (XSθ)) = π · fa(XSθ). So π · fa(XSθ) ⊆T. π is a bijection, so fa(XSθ) ⊆π-1 · T and θ ∈ Sol(XS ⊑π-1 · T, Inc). Conversely, if θ ∈ Sol(XS ⊑ π-1 · T, Inc) then θ ∈ Sol(π · XS ⊑T, Inc) follows by a similar argument.

Lemma 23

Support inclusion problem simplification is confluent and terminating. Write nf (Inc) for the unique =⇒-normal form of Inc.

Proof

(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.

Definition 24

Call Inc consistent when a ⊑T ∉ nf (Inc) for all atoms a and permission sorts T. Call Inc solvable when Sol(Inc) ≠ ∅. Call Inc non-trivial when nf (Inc) ≠ ∅.

Lemma 25

If Inc is consistent then all inc ∈ nf (Inc) have the form XS ⊑T where S ⊈T.

Definition 26

Define fV (Inc) by fV (Inc) = ⋃{fV (r) | ∃T.r ⊑T ∈ Inc}.

Definition 27

Let V range over finite sets of unknowns.

Suppose Inc is consistent. For every XS ∈V make a fixed but arbitrary choice of X′S′ such that X′S′∉V and S′ = S ∩⋂{T | XS ⊑T ∈ nf (Inc)}.

We make our choice injectively; for distinct XS ∈ fV (Inc) and Y T ∈ fV (Inc), we choose X′S′ and Y ′T ′ distinct. It will be convenient to write V′V Inc for the set of our choices {X′S′| XS ∈V}. Define a substitution ρV Inc by:

ρV Inc(XS) ≡id · X′S′if XS ∈V ρV Inc(Y T ) ≡id · Y T otherwise.
Lemma 28

If Inc is consistent then ρV Inc ∈ Sol(Inc). (‘ρV Inc solves Inc’.)

Proof

Suppose Inc is a =⇒-normal form. If XS ⊑T ∈ Inc then ρV Inc(X) = id · X′S′ for an S′ which, by construction, satisfies S′ ⊆T. 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.

Theorem 29

Inc is consistent if and only if Inc is solvable.

Proof

By Lemma 22 Sol(Inc) = Sol(nf (Inc)), so it suffices to show the result for the special case that Inc is a =⇒-normal form.

Suppose Inc is inconsistent, so nf (Inc) contains some support inclusions of the form a ⊑T where a ∉T. aθ ≡a always, so there is no substitution θ such that aθ ⊆T. Conversely, if Inc is consistent the result follows by Lemma 28.

Definition 30

Suppose that Inc is consistent, fV (Inc) ⊆V, and θ ∈ Sol(Inc). Define a substitution θ-ρV Inc by:

– (θ-ρV Inc)(X′S′) ≡θ(XS) if XS ∈V and ρV Inc(XS) ≡ id · X′S′.

– (θ-ρV Inc)(XS) ≡θ(XS) if XS ∉V.

Lemma 31

Suppose θ ∈ Sol(Inc) and fV (Inc) ⊆V. Then ρV Inc exists, and θ-ρV Inc is a substitution.

Proof

If θ ∈ Sol(Inc) then Inc is solvable (Definition 20). By Theorem 29, Inc is consistent. Therefore ρV Inc from Definition 27 exists. We now show that fa((θ-ρV Inc)(X′S′)) ⊆S always. We reason by cases:

− The case that id · X′S′≡ρV Inc(XS) for XS ∈V.

It is not hard to prove that fV (nf (Inc)) ⊆ fV (Inc) always, so fV (nf (Inc)) ⊆V. There are two sub-cases:

− The case XS ∉ fV (nf (Inc)). Then S = S′ and (θ-ρV Inc)(X′S) = θ(XS).

By assumption fa(θ(XS)) ⊆S.

− The case XS ∈ fV (nf (Inc)). θ ∈ Sol(Inc) so by Lemma 22 θ ∈ Sol(nf (Inc)) and so fa(θ(XS)) ⊆T for every T such that XS ⊑T ∈ nf (Inc). By definition S′ = ⋂{T | XS ⊑T ∈ nf (Inc)} and the result follows.

− Otherwise, (θ-ρV Inc)(XS) ≡θ(XS). By assumption fa(θ(XS)) ⊆S.

Theorem 32

Suppose θ ∈ Sol(Inc) and suppose fV (Inc) ⊆V. Then θ(XS) ≡ (ρV Inc ◦ (θ-ρV Inc))(XS) for every XS ∈V.

Proof

ρ(XS) ≡ id · X′S for some fresh X′S ∉V, and (θ-ρV Inc)(X′S) ≡θ(XS). The result follows by Lemma 9.

5 Permissive nominal unification problems

5.1 Problems, solutions, the unification algorithm

Definition 33

An equality (problem) is a pair r?= s. A problem Pr is a finite multiset of equalities. Define Prθ by Prθ = {rθ?= sθ | r?= s ∈Pr}.

Definition 34

θ solves Pr when r?= s ∈Pr implies rθ =α sθ. Write Sol(Pr) for the set of solutions to Pr. Call Pr solvable when Sol(Pr) is non-empty.

A solution to Pr ‘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’.

Lemma 35

θ ◦θ′ ∈ Sol(Pr) if and only if θ′ ∈ Sol(Prθ).

Proof

Suppose θ ◦θ′ ∈ Sol(Pr) and r?= s ∈Pr. We reason using Theorem 19: (rθ)θ′ ≡r(θ ◦θ′) =α s(θ ◦θ′) ≡ (sθ)θ′. The reverse implication is similar.

Definition 36

If Pr is a problem, define a support inclusion problem Pr⊑ by: Pr⊑= {r ⊑ fa(s), s ⊑ fa(r) | r?= s ∈Pr}.

Definition 37

Define a simplification rewrite relation V; Pr =⇒V′; Pr′ by:

(?=a) V; a?= a, Pr =⇒ V; Pr(?=f) V; f(r1, . . .)?= f(s1, . . .), Pr =⇒ V; r1?= s1, . . . , Pr(?=[a]) V; [a]r?= [a]s, Pr =⇒ V; r?= s, Pr(?=[b]) V; [a]r?= [b]s, Pr =⇒ V; (b a) · r?= s, Pr (b ∉fa(r))(?=X) V; π · XS?= π · XS, Pr =⇒ V; Pr(I1) V; π · XS?= s, Pr[XS:=π-1·s]=⇒ V; Pr[XS:=π-1 · s] (XS ∉fV (s), fa(s) ⊆π · S)(I2) V; r?= π · XS, Pr[XS:=π-1·r]=⇒ V; Pr[XS:=π-1 · r] (XS ∉fV (r), fa(r) ⊆π · S)(I3) V; PrρV Pr⊑=⇒ V ∪V′V Pr⊑; Pr ρV Pr⊑(Pr⊑consistent and non-trivial)

Call (?=a), (?=f), (?=[a]), (?=[b]), and (?=X) non-instantiating rules.

Call (I1), (I2), and (I3) instantiating rules.

We insist Pr⊑ is non-trivial (Definition 20) to avoid indefinite rewrites. We insist Pr⊑ is consistent so ρV Pr⊑ exists. ρV Pr⊑ and V′V Pr⊑ are defined in Definition 27.

Lemma 38

If Pr =⇒Pr′ by a non-instantiating rule then Sol(Pr) = Sol(Pr′).

Proof

The interesting case is (?=[b]). Suppose that Pr = [a]r?= [b]s, Pr′′ and b ∉ fa(r) and so Pr =⇒ (b a) · r?= s, Pr′′ with (?=[b]). Then:

− Suppose ([a]r)θ =α ([b]s)θ. By Definition 14 [a](rθ) =α [b](sθ). By the structure of the rules in Definition 8, (b a)·(rθ) =α sθ. By Lemma 16 and Theorem 11, ((b a) · r)θ =α sθ.

− Suppose ((b a)·r)θ =α sθ. By Lemma 16 and Theorem 11, (b a)·(rθ) =α sθ. By Theorem 15 b ∉ fa(rθ). Therefore by (=α[b]) [a](rθ) =α [b](sθ). By Definition 14 [a](rθ) =α [b](sθ), as required.

Definition 39

Define fV (Pr) = ⋃{fV (r) ∪ fV (s) | r?= s ∈Pr}.

Definition 40

Suppose V is a set of unknowns. Define θ|V by:4

θ|V(X) ≡θ(X) if X ∈V θ|V(X) ≡id · X otherwise.
Definition 41

If Pr is a problem, define a unification algorithm by:

1. Rewrite fV (Pr); Pr 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 V′; ∅, we succeed and return θ|V where θ is the functional composition of all the substitutions labelling rewrites (we take θ = id if there are none). Otherwise, we fail.

Lemma 42

The algorithm of Definition 41 always terminates.

Proof

By an easy argument using a notion of the size of a unification problem.

Lemma 43

Suppose θ(XS) =α θ′(XS) for all XS ∈ fV (Pr). Then θ ∈ Sol(Pr) if and only if θ′ ∈ Sol(Pr).

Proof

Unpacking Definition 34 it suffices to show that rθ =α sθ if and only if rθ′ =α sθ′, for every r?= s ∈Pr. This is easy using Theorem 17 and the fact by construction (Definition 39) that fV (r) ⊆ fV (Pr) and fV (s) ⊆ fV (Pr).

Definition 44

Write θ-XS for the substitution such that:

(θ-XS)(XS) ≡id · XSand (θ-XS)(Y T ) ≡θ(Y T ) for all other Y T
Theorem 45

Suppose (id · XS)θ =α sθ and XS ∉ fV (s). Then:

θ(XS) =α ([XS:=s]◦(θ-XS))(XS) and θ(Y T ) =α ([XS:=s]◦(θ-XS))(Y T )
Proof

We reason as follows:

([XS:=s]◦(θ-XS))(XS) ≡ s(θ-XS) Definition 14≡ sθ XS ∉fV (s), Theorem 17=αθ(XS) Assumption([XS:=s]◦(θ-XS))(Y T ) ≡ (θ-XS)(Y T ) Definition 18≡ θ(Y T ) Definition 44

5.2 Simplification rewrites calculate principal solutions

Definition 46

Write θ1 ≤θ2 when there exists θ′ such that XSθ2 =α XS(θ1◦θ′) always. We call ≤ the instantiation ordering.

Definition 47

A principal (or most general) solution to a problem Pr is a solution θ ∈ Sol(Pr) such that θ ≤θ′ for all other θ′ ∈ Sol(Pr).

Our main results are Theorems 48 — the unification algorithm from Definition 41 calculates a solution — and 53 — the solution it calculates, is principal.

Theorem 48

Suppose fV (Pr) ⊆V. If V; Prθ=⇒∗V′; ∅ then θ|V ∈ Sol(Pr).

Proof

By induction on the length of the path in θ=⇒∗. If it has length 0 then Pr = ∅ and θ ≡ id and the result follows. Otherwise, there are three cases:

− The non-instantiating case. Suppose V; Pr =⇒V; Pr′′θ=⇒∗V′; ∅. By easy calculations fV (Pr′′) ⊆V. By inductive hypothesis θ|V ∈ Sol(Pr′′). By Lemma 38, θ|V ∈ Sol(Pr).

− The case of (I1) or (I2). Suppose V; Prχ=⇒V; Prχθ′=⇒∗V′; ∅. By easy calculations fV (Prχ) ⊆V. By inductive hypothesis θ′|V ∈ Sol(Prχ). It is a fact that (χ ◦θ′)|V = χ ◦ (θ′|V). By Lemma 35, (χ ◦θ′)|V ∈ Sol(Pr).

− The case of (I3). Suppose V; Prρ=⇒V′; Prρθ′=⇒∗V′′; ∅. By easy calculations fV (Prρ) ⊆V′. By inductive hypothesis θ′|V′ ∈ Sol(Prρ). By Lemma 35, ρ ◦ (θ′|V′) ∈ Sol(Pr). It is a fact that ρ ◦ (θ′|V′) = (ρ ◦θ′)|V′. By Lemma 43, (ρ ◦θ′)|V ∈ Sol(Pr).

Lemma 49

If θ1 ≤θ2 then θ◦θ1 ≤θ◦θ2.

Proof

By Definition 46 θ′ exists such that XSθ2 =α XS(θ1◦θ′) always. We use Theorems 19 and 17: XS(θ◦θ2) ≡ (XSθ)θ2 =α (XSθ)(θ1 ◦θ′) ≡XS((θ◦θ1)◦θ′)

Lemma 50

Suppose XSθ2 =α XSθ′ 2 always. Then θ1 ≤θ2 implies θ1 ≤θ′ 2.

Proof

By a routine calculation unpacking Definition 46 and using Theorem 11.

Lemma 51

If r =α s then fa(r) = fa(s).

Lemma 52

If θ ∈ Sol(Pr) (Definition 34) then θ ∈ Sol(Pr⊑) (Definition 20).

Proof

Using Lemma 51.

Theorem 53

Suppose fV (Pr) ⊆V. If V; Prθ=⇒∗V′; ∅ then θ|V is a principal solution to Pr.

Proof

By Theorem 48 θ|V ∈ Sol(Pr). We prove that θ|V is principal by induction on the path length of V; Prθ=⇒∗V′; ∅.

− Length 0. So Pr = ∅ and θ = id|V. id|V ≤θ′|V is a fact of Definition 46.

− Length k + 1. We consider the rules in Definition 37.

− The non-instantiating case. Suppose V; Pr =⇒V; Pr′θ=⇒∗V′; ∅ where V; Pr =⇒V; Pr′ is non-instantiating. By inductive hypothesis, θ|V is a principal solution of Pr′. By Lemma 38 θ|V is also a principal solution of Pr.

− The case (I1). Suppose fa(s)⊆π·S and XS∉ fV (s). Write χ=[XS:=π-1·s]. Suppose Pr=π·XS?=s,Pr′′ so that V; π·XS?=s,Pr′′χ=⇒V; Pr′′χ and

suppose V; Pr′′χθ′′=⇒∗V′; ∅ and θ′|V ∈ Sol(Pr). By Theorem 48 θ′′|V ∈ Sol(Pr′′χ). It is routine to check that fV (Pr′′χ) ⊆V. By Theorem 45 and Lemma 43, χ◦(θ′|V-XS) ∈ Sol(Pr). It is a fact that (θ′|V-XS) = (θ′-XS)|V so by Lemma 35, (θ′−XS)|V ∈ Sol(Pr′′χ). By inductive hypothesis θ′′|V ≤ (θ′-XS)|V. By Lemma 49 we have χ◦(θ′′|V) ≤ χ◦(θ′-XS)|V. Now by assumption fV (s) ⊆V and X ∈V, and it follows that χ◦(θ′′|V) = (χ◦θ′′)|V. Also, it is a fact that (θ′−XS)|V = θ′|V-XS. By Theorem 45 and Lemma 50, (χ◦θ′′)|V ≤θ′|V as required.

− The case (I2) is similar to the case of (I1).

− The case (I3). Suppose Pr⊑ is consistent and non-trivial. Write ρ = ρV Pr⊑,

so that V; Prρ=⇒V′′; Prρ and V′′; Prρθ′′=⇒∗V′; ∅ and suppose θ′|V ∈ Sol(Pr).

By Theorem 48 θ′′|V′′∈ Sol(Prρ). V′′ =V∪V′VPr⊑, so fV (Prρ) ⊆V′′. By

Lemma 52 θ′|V ∈ Sol(Pr⊑). By Theorem 32 and Lemma 43 it follows that ρ◦(θ′|V-ρ) ∈ Sol(Pr). By Lemma 35, θ′|V-ρ ∈ Sol(Prρ). By inductive hypothesis θ′′|V ≤θ′|V-ρ. By Lemma 49 ρ◦θ′′|V ≤ρ◦(θ′|V-ρ). It is a fact that ρ◦(θ′′|V) = (ρ◦θ′′)|V. By Theorem 32 and Lemma 50, (ρ◦θ′′)|V ≤ θ′|V as required.

Lemma 54

If V; Prχ=⇒V; Pr′ with (I1) or (I2) then θ ∈ Sol(Pr) implies θ-χ ∈ Sol(Pr′). Similarly, if V; Prρ=⇒V′; Pr′ with (I3) then θ ∈ Sol(Pr) implies θ-ρ ∈ Sol(Pr′).

Proof

Suppose fa(s)⊆π · S and XS ∉ fV (s). Write χ=[XS:=π-1 · s]. Suppose Pr = π·XS?= s, Pr′′ so that V; π·XS?= s, Pr′′χ=⇒V; Pr′′χ. Now suppose θ ∈ Sol(Pr). By Lemma 43 and Theorem 45, χ◦(θ-XS)) ∈ Sol(Pr). By Lemma 35, θ-XS ∈ Sol(Prχ). It follows that θ-XS ∈ Sol(Pr′′χ) as required.

Suppose Pr⊑ is consistent and non-trivial. Write ρ = ρV Pr⊑, so that V; Prρ=⇒ V′′; Prρ. Now suppose θ ∈ Sol(Pr). By Lemma 43 and Theorem 32, ρ◦(θ-ρ) ∈ Sol(Pr). By Lemma 35, θ-ρ ∈ Sol(Prρ) as required.

Theorem 55

Given a problem Pr, if the algorithm of Definition 41 succeeds then it returns a principal solution; if it fails then there is no solution.

Proof

If the algorithm succeeds we use Theorem 53. Otherwise, the algorithm generates an element of the form f(r1, . . . , rn) ?= f(r′ 1, . . . , r′ n′) where n ≠ n′, f(. . .) ?= g(. . .), f(. . .) ?= [a]s, f(. . .) ?= a, [a]r =α a, [a]r =α b, a?= b, a Pr such that Pr⊑ is inconsistent, or π · XS?= r or r?= π · XS where XS ∈ fV (r). By arguments on syntax and size of syntax, no solution to the reduced problem exists. It follows by Lemma 54 that no solution to Pr 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’ A such that A is infinite and A \ A 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 A \ 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 S; nominal terms do not.

Definition 56

Fix a countably infinite set of nominal atoms, ˙A. ˙a, ˙b, ˙c, . . . will range over distinct nominal atoms. Fix a bijection ι between ˙A and comb (Definition 2). Fix a countably infinite set of nominal unknowns. ˙X, ˙Y , ˙Z, . . . will range over distinct nominal unknowns. A nominal permutation is a bijection ˙π on ˙A such that {˙a | ˙π(˙a) ≠ ˙a} is finite. ˙π, ˙π′, ˙π′′, . . . will range over permutations.

Write ˙π-1 for the inverse of ˙π, ˙id for the identity permutation, and ˙π◦˙π′ for function composition, as is standard. For example, ( ˙π◦˙π′)(˙a) = ˙π( ˙π′(˙a))

Definition 57

Define nominal terms by ˙r, ˙s, ˙t ::= ˙a | ˙π · ˙X | [˙a] ˙r | f( ˙r, . . . , ˙r), with permutation action

˙π·˙a ≡˙π(˙a) ˙π·f( ˙r1, . . .) ≡f( ˙π· ˙r1, . . .) ˙π·[˙a] ˙r ≡[ ˙π(˙a)]( ˙π· ˙r) ˙π·( ˙π′· ˙X) ≡( ˙π◦˙π′)· ˙X

Write ≡ for syntactic identity. f ranges over term-formers (Definition 1).

Definition 58

A freshness is a pair ˙a# ˙r. An equality is a pair ˙r = ˙s. A freshness context is a finite set of freshnesses of the form ˙a# ˙X. Define derivable freshness and derivable equality by:

(#ḃ)∆⊢˙a#˙b∆⊢˙a# ˙ri(1 ≤i ≤n) (#f) ∆⊢˙a#f( ˙r1, . . . , ˙rn)(#[ȧ])∆⊢˙a#[˙a] ˙r∆⊢˙a# ˙r(#[ḃ])∆⊢˙a#[˙b] ˙r( ˙π-1(˙a)# ˙X ∈∆) (#Ẋ) ∆⊢˙a#π · ˙X
(=ȧ)∆⊢˙a = ˙a∆⊢˙ri = ˙si(1 ≤i ≤n)(=f)∆⊢f( ˙r1, . . . , ˙rn) = f( ˙s1, . . . , ˙sn)∆⊢˙r = ˙s(=[ȧ])∆⊢[˙a] ˙r = [˙a] ˙s∆⊢(˙b ˙a) · ˙r = ˙s ∆⊢˙b# ˙r (=[ḃ]) ∆⊢[˙a] ˙r = [˙b] ˙s(˙a# ˙X ∈∆for every ˙π(˙a) ≠ ˙π′(˙a)) (=Ẋ) ∆⊢˙π · ˙X = ˙π′ · ˙X

Definition 58 repeats [UPG04, Figure 2], up to differences in presentation. A full discussion of nominal terms is in [UPG04]. ∆⊢˙a# ˙r corresponds with ‘a ∉ fa(r)’ (made formal in Lemma 61), and ∆⊢˙r = ˙s corresponds with ‘r =α s’ (see Theorems 62 and 63). ∆ plays the role of permissions sorts, but is part of the judgement-form.

Definition 59

Define a mapping ⟦ ˙π⟧ from nominal permutations to permissive nominal permutations by ⟦ ˙π⟧(ι(˙a)) = ι( ˙π(˙a)) and ⟦ ˙π⟧(c) = c for all c ∈A\comb. Define an interpretation ⟦ ˙r⟧∆ by:

⟦˙a⟧∆≡ι(˙a) ⟦f( ˙r1, . . . , ˙rn)⟧∆≡f(⟦ ˙r1⟧∆, . . . , ⟦ ˙rn⟧∆) ⟦[˙a] ˙r⟧∆≡[ι(˙a)]⟦ ˙r⟧∆⟦ ˙π · ˙X⟧∆≡⟦ ˙π⟧ · XSwhere S = comb \ {ι(˙a) | ˙a# ˙X ∈∆}

Here, we make a fixed but arbitrary choice of XS for each ˙X, injectively so that ⟦X ˙⟧∆ and ⟦Y ˙⟧∆ are always distinct.

Lemma 60

⟦ ˙π⟧ · ⟦ ˙r⟧∆≡⟦ ˙π · ˙r⟧∆

Lemma 61

ι(˙a)∉fa(⟦ ˙r⟧∆) if and only if ∆⊢˙a# ˙r. b∉fa(⟦ ˙r⟧∆) if b ∈A\comb.

Theorem 62

⟦ ˙r⟧∆=α ⟦ ˙s⟧∆ implies ∆⊢˙r = ˙s.

Proof

Induction on the derivation of ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆. We consider some cases:

− The case (=α[b]). Suppose (ι(˙b) ι(˙a))·⟦ ˙r⟧∆=α ⟦ ˙s⟧∆ and ι(˙b) ∉ fa(⟦ ˙r⟧∆). By Lemmas 60 and 61 ⟦(˙b ˙a) · ˙r⟧∆=α ⟦ ˙s⟧∆ and ∆⊢˙b# ˙r. By inductive hypothesis ∆⊢ (˙b ˙a) · ˙r = ˙s. We use (=[ḃ ]).

− The case (=αX). Suppose ⟦ ˙π⟧|S = ⟦ ˙π′⟧|S where S = comb\{ι(˙a) | ˙a# ˙X∈∆}. ι is injective, so a# ˙X ∈∆ for all ˙a such that ˙π(˙a) ≠ ˙π′(˙a). We use (=Ẋ ).

Theorem 63

If ∆⊢˙r = ˙s then ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆.

Proof

Induction on the derivation of ∆⊢˙r = ˙s. We consider some cases:

− The case (=[ ḃ]). Suppose ∆⊢ (˙b ˙a) · ˙r = ˙s and ∆⊢˙b# ˙r. By inductive hypothesis and Lemma 60, (˙b ˙a) · ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆. By Lemma 61 ι(˙b) ∉ fa(⟦ ˙r⟧∆). We use (?=[b]).

− The case (= Ẋ). Recall that ⟦ ˙π · ˙X⟧∆= ⟦ ˙π⟧ · XS and ⟦ ˙π′ · ˙X⟧∆= ⟦ ˙π′⟧ · XS where S = comb \ {ι(˙a) | ˙a# ˙X ∈∆}. Suppose ˙π(˙a) ≠ ˙π′(˙a) implies ∆⊢˙a# ˙X.

Using Lemma 61, ⟦ ˙π⟧(ι(˙a)) ≠ ⟦ ˙π′⟧(ι(˙a)) implies ι(˙a) ∉S. We use (?=X).

Definition 64

A substitution ˙θ is a function from nominal unknowns to nominal terms such that {X ˙| ˙θ( ˙X) ≢ ˙id · ˙X} is finite. ˙θ, ˙θ′, ˙θ′′, . . . will range over nominal substitutions. Write ˙id for the identity, mapping ˙X to ˙id · ˙X.

Definition 65

Define a substitution action on nominal terms by:

˙a ˙θ ≡˙a f( ˙r1, . . . , ˙rn) ˙θ ≡f( ˙r1 ˙θ, . . . , ˙rn ˙θ) ([˙a] ˙r) ˙θ ≡[˙a]( ˙r ˙θ) ( ˙π· ˙X) ˙θ ≡˙π· ˙θ( ˙X)
Definition 66

Following [UPG04, Definition 3.1], a unification problem ˙Pr is a finite multiset of freshnesses and equalities. A solution to ˙Pr is a pair (∆, ˙θ) such that ∆⊢˙a# ˙r ˙θ for every ˙a# ˙r ∈˙Pr, and ∆⊢˙rθ = ˙sθ for every ˙r = ˙s ∈˙Pr.

Definition 67

We extend the interpretation of Definition 59 to solutions by:

⟦(∆, ˙θ)⟧(XS) ≡⟦ ˙θ(X)⟧∆if id·XS≡⟦X⟧∆⟦(∆, ˙θ)⟧(Y T ) ≡id·Y T otherwise
Lemma 68

⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ ≡⟦ ˙r ˙θ⟧∆.

Proof

By inductions on ˙r. We consider the case ˙π· ˙X, and reason using Lemma 60:

⟦( ˙π · ˙X) ˙θ⟧∆≡⟦ ˙π · ˙θ( ˙X)⟧∆≡⟦ ˙π⟧ · ⟦ ˙θ( ˙X)⟧∆≡⟦ ˙π⟧ · ⟦ ˙θ⟧(⟦ ˙X⟧∆)
Definition 69

Define ⟦Pr ˙⟧∆ by mapping ˙r = ˙s to ⟦ ˙r⟧∆?= ⟦ ˙s⟧∆ and mapping ˙a# ˙r to (b ι(˙a)) · ⟦ ˙r⟧∆?= ⟦ ˙r⟧∆, for some choice of fresh b (so b ∉ fa(⟦ ˙r⟧∆); in fact, it suffices to choose some b ∉ comb).

Lemma 70

Suppose b ∉ fa(r). Then a ∉ fa(r) if and only if (b a) · r =α r.

Theorem 71

(∆, ˙θ) solves ˙Pr if and only if ⟦(∆, ˙θ)⟧ solves ⟦ ˙Pr⟧∆.

Proof

We sketch the necessary reasoning.

Suppose ∆⊢˙r ˙θ = ˙sθ ˙. By Lemma 68 and Theorem 63, ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ =α ⟦ ˙s⟧∆⟦(∆, ˙θ)⟧. The reverse direction uses Theorem 62.

Suppose ∆⊢a# ˙r ˙θ. By Lemmas 61, 70, 68, and 16 ((b ι(˙a))·⟦ ˙r⟧∆)⟦(∆, ˙θ)⟧ =α ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧. Here, we use the b chosen fresh in Definition 69. The reverse direction uses the same results.

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 ˙X from Section 6 may be more simply and directly useful than Xcomb. 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 β0 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 c ∉ comb; then the rewrite Xcomb →Xcomb cannot trigger the rewrite U comb∪{c} →U comb∪{c} because there is no π such that π · comb = comb ∪{c}, and likewise there is no substitution σ, because of the side-condition that fa(σ(Xcomb)) ⊆ comb. It may therefore be desirable to consider only permissions sorts of the form comb \ A for A ⊆A 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 14th 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 15th 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(θ(XS)) ⊆S’ 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 ‘∇⊢a#θ(t)’ in Definition 3.1 of [UPG04]. More on this in Section 6. ↩

4 We overload |, for technical convenience: π|S (Definition 8) is partial and θ|V is total. ↩