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

Meta-variables as infinite lists in nominal terms unification and rewriting

Murdoch J. Gabbay

Source watermark: DRAFT

gabbay.org.uk

Abstract

We consider the theories of nominal unification and rewriting for a new and simplified presentation of nominal terms, based on modelling moderated nominal unknowns as infinite but decidable tuples of atoms. Nominal terms α-equivalence becomes a special case of ordinary α-equivalence, definitions and proofs come closer to those of traditional syntax, proofs are simplified, and some new properties are obtained.

Key words: Nominal terms, alpha-equivalence, binding, nominal unification, nominal rewriting, nominal algebra, permissive-nominal logic, logical frameworks, foundations

May 17, 2012

1. Introduction

In this paper we simplify nominal terms, by modelling nominal unknowns as infinite tuples of distinct atoms. We find that by doing this, α-equivalence becomes a special case of ordinary α-equivalence; working with the syntax becomes significantly easier; and some new mathematical properties appear.

The idea of modelling nominal unknowns as infinite tuples was introduced in [28] and explored further in [23].

The emphasis in this paper is on the practical and computational aspects of this model (and it is self-contained). We address questions like: Can we compute on these terms? Is it easier to express known proofs and properties of nominal terms? Do any extra properties become true? Our answer is: mostly, yes.

Nominal terms and their unification and rewriting were introduced by the author and others in [38] and [12] as a way of studying nominal sets (called equivariant Fraenkel-Mostowski sets in [30]).

Nominal terms are intuitively ‘first-order syntax plus names and binding’. In nominal terms, term-formers can bind names in their arguments but (thanks to an intended semantics in nominal sets as described in [30]) they have the flavour of first-order rather than higher-order syntax. Nominal terms unification possesses the good computational properties of first-order unification: decidability, and most general unifiers can be computed [38]. For more on unification of nominal terms see [3, 32, 4, 33].

Nominal terms also have some specific technical properties, including two levels of variable (atoms and unknowns), a capturing substitution action, a notion of state called a freshness context, and a non-standard notion of α-equivalence. The interested reader is referred to an extensive literature [38, 12, 6, 24].

It matters to try making nominal terms as simple as possible. Developers of nominal terms’ theory, including but not limited to this author, may benefit from a new presentation of the objects of interest—especially if this leads to simpler proofs. Also potential users of nominal terms may benefit from alternative presentations, especially if they look more like what we are used to seeing in ‘ordinary’ syntax.

We discuss in the body of the paper how complicated our infinite tuples are to work with. We will argue that what matters is not a infinity per se but whether it admits a compact representation: ours will.

Convenient properties of our model

Our new model of nominal terms has convenient mathematical properties:

• α-equivalence can be defined in one line as we quotient by binding. See Definition 2.19. This is less detailed and less formal than in [38], but this is acceptable

because the usual theory of α-equivalence on syntax is so well-known, and by the presentation of this paper we have been able to ‘plug into’ it.

• Substitutions have a (in this author’s opinion) beautiful characterisation as equivariant functions; the ‘freshness conditions’ of substitutions on nominal terms emerge as a corollary; see Lemma 2.33.

• Permutations are generated by swappings as usual—and also a shift permutation δ, which is new (Definition 2.4). δ corresponds to a de Bruijn shift function ↑ and presheaf reindexing map up, but it is invertible and we use it in a nominal context. See Lemma 2.49 and rule (IF) of Figure 1.

• The simplification rules for problems (Figure 1) are new.

• The treatment of closed terms is also new and can be compared with that in [12]; see Section 5.

It is also possible to extend the syntax of this paper with quantification over unknowns. Thus the syntax of Permissive-Nominal Logic [22] which has a quantifier ∀X for unknowns (which in that paper were modelled as a syntactic class of symbols) can fit into an extension of the model of unknowns explored in this paper.

In brief, in this paper we present nominal terms, but abstractly and as the reader has (probably) not seen them before. The reward is a presentation that more closely imitates traditional syntax, and perhaps has better maths, easier proofs, and more theorems.

2. Nominal terms

2.1. Atoms, permutations, permission sets

Following [11] we develop a theory of permission sets. A permission sets splits the set of atoms into two equally sized halves: it is used like a type, controlling the free symbols in a term. Intuitively, one half is ‘the atoms that are permitted free’, the other half is ‘the atoms that must be bound’.

We also develop a theory of permutations, which we use later to handle α-equivalence (one distinctive feature of nominal techniques is that we take permutations as primitive instead of renamings or substitutions; permutations are invertible and this turns out to be useful). Unlike what the reader may have previously seen, our permutations will not be finite. Why this is the case will become clear later.

Definition 2.1

Fix two disjoint countably infinite sets 𝔸< and 𝔸> of atoms and write

𝔸 = 𝔸< ∪𝔸>.

a, b, c, . . . will range over distinct elements of 𝔸; we call this the permutative convention.

Remark 2.2

The reader can think of 𝔸< intuitively as atoms that are ‘capturable’ and atoms in 𝔸> as atoms that are ‘not capturable’. This is reminiscent of some treatments of syntax where a formal distinction is made between ‘names that exist to be bound’ and ‘names that exist to be free’. See for instance the freie and gebundene Gegenstansvariable of Gentzen [31, Section 1], and the individual variables and parameters of Prawitz [34, Section 1], or Smullyan [36, Chapter IV, Section 1].

An important caveat is that permutations and permission sets, developed below, can and will move atoms between these worlds. However, no permutation can move all the atoms in 𝔸< into 𝔸> at once. So it would be misleading to examine an individual atom and ask ‘is this atom capturable?’. The interest of 𝔸< and 𝔸> is that they guarantee enough—countably infinitely many—that we cannot exhaust supplies of either type of atom.

These key points will become clearer as the maths is developed.

Definition 2.3

Fix a bijection from non-positive integers {. . . , -3, -2, -1, 0} to 𝔸<. Fix a bijection from positive integers {1, 2, . . .} to 𝔸>. Write their combination f; this is a bijection from integers to atoms.

Definition 2.4

Given a, b ∈𝔸 write (a b) for the swapping bijection on atoms specified by:

a↦ →b b↦ →a c↦ →c

Recall that by our permutative convention a, b, and c are distinct. By convention (a a) will denote the identity function on atoms id.

Write δ for the shift permutation which maps f(i) to f(i−1) for i ≤ 0, and f(2i) to f(2(i−1)) and f(2i+1) to f(2i+1) for i ≥ 1. So:

f(i)↦ →f(i−1) i ≤0f(2i)↦ →f(2(i−1)) i ≥1f(2i+1)↦ →f(2i+1) i ≥0
Example 2.5

We illustrate fragments of the actions of the swapping (f(0) f(1)) and δ:

f(-7) f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6) f(7)f(-7) f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6) f(7)
Remark 2.6

Swappings are familiar from [30]. Shift permutations δ are new (though infinite permutations in general have been considered in a nominal setting in [20]).

δ has the following properties:

• There are infinitely many a such that δ(a) = a, so we can always choose an atom ‘fresh’ for δ (we use this for instance in part 2 of Definition 2.44).

• δ bijects 𝔸< with 𝔸< \ {f(0)}. In this sense it creates a ‘fresh’ atom.

If we think of 𝔸< as a namespace—an environment of ‘generated names’—and 𝔸> as a space of names yet to be generated, then δ expresses that adding/deleting a name to/from the universe of countably infinitely many names, makes no difference up to bijection.

More on why δ is useful in Subsection 2.6.

Definition 2.7

Let permutations be generated as a group by swappings (a b) and shift δ.1 π and π′ will range over permutations.

Define nontriv(π) by

nontriv(π) = {a | π(a) ≠ a}.

Call π finite when it is in the subgroup generated by swappings. It is easy to see that π is finite if and only if nontriv(π) is finite.

Write π◦π′ for the composition of π and π′ (so (π ◦π′)(a) = π(π′(a))). Write id for the identity permutation (so id(a) = a always).

Lemma 2.8

(a b) ◦δ = δ ◦ (δ-1(a) δ-1(b)).

As a corollary, any π may be uniquely written as δi ◦π′, and concretely represented as the pair (i, π′), for some i ∈ℤ and some finite π′.

Proof

The first part is a fact of groups. The second part follows since permutations in Definition 2.7 are generated as a group by swapping permutation (a b) and shift permutation δ.End of proof

Definition 2.9

Give sets of atoms A ⊆𝔸 the pointwise permutation action given by π·A = {π(a) | a ∈A}.

Definition 2.10

A permission set S is a set of the form π·𝔸<.

S, T will range over permission sets.

2.2. Unknowns

Remark 2.11

The slogan of this subsection is:

An unknown X is a well-ordering of a permission set.

Permission sets are infinite; the reader who does not care how we might represent a well-ordering inside a (finite) computing machine, or decide equality of two representations, can stop reading this subsection now, because that is all we will discuss.

The problem is that there are uncountably many such well-orderings and no way to represent them all in an implementation. However, some well-orderings do have good computational properties. In this subsection we exhibit a subset of the set of all well-orderings of permission sets such that:

• Each well-ordering has a compact and finite representation and equality is quickly decidable (Corollary 2.17).

• The subset is closed under the natural permutation action (this is fairly evident by construction but is pointed out explicitly after this action is defined, in Remark 2.24).

• For each permission set there are infinitely many well-orderings that are not related by any permutation (Proposition 2.18).

There are many such subsets; we just need to show concretely that one exists. Nothing in the rest of this paper will depend on the concrete calculations to follow.

Definition 2.12

For each prime number p ≥ 2 define a bijection on non-positive integers ϖp which for every i ≥ 0 maps -p2∗(i+1) to -p2∗i+1 and maps -p2∗i+1 to -p2∗(i+1), and is the identity elsewhere:

-p2∗(i+1)↦ →-p2∗i+1i ≥0-p2∗i+1↦ →-p2∗(i+1)i ≥0n↦ →n other n

Let ϖ range over the group generated by the ϖp.

Example 2.13

We illustrate initial fragments of the actions of ϖ2 and ϖ3:

-16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0-16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0
Lemma 2.14

Every ϖ may be represented canonically as a finite list of unique generating elements in numerical order.

Proof

The generators biject with the prime numbers and form an involutive and com-mutative group.End of proof

Definition 2.15

A level 2 variable or unknown X is a bijection from non-positive integers to a permission set π·𝔸<, of the form π ◦f ◦ϖ.

We may consider X as a tuple and write xi for X(i) and write X = (xi)i≤0 or even X = (. . . , x-5, x-4, x-3, x-2, x-1, x0).

Write orb(X) for the unique ϖ such that X = π ◦f ◦ϖ for some π.

X, Y , Z will range over unknowns. By convention, X and Y will range over unknowns such that orb(X) and orb(Y) are distinct; this is a form of permutative convention.

Write pmss(X) for the permission set of X defined by {xi | i ≤ 0}.

Lemma 2.16

1. If π ◦f ◦ϖ = π′ ◦f ◦ϖ′ then ϖ = ϖ′.2

2. If π ◦f ◦ϖ = π′ ◦f ◦ϖ then π(a) = π′(a) for every a ∈𝔸<.

As a corollary, orb(X) is well-defined and orb(π·X) = orb(X).

Proof

A fact of the way we constructed the groups that π and ϖ inhabit.End of proof

Corollary 2.17

X may be finitely represented as a pair (π, P) where π is a permutation and P is a finite set of prime numbers. As a corollary, equality of unknowns is decidable and orb(X) is quickly calculated from a reasonable finite representation using second projection.

Proof

From Lemmas 2.8, 2.14 and 2.16.End of proof

Proposition 2.18

For every permission set S there are infinitely many unknowns X with distinct permutation orbits such that pmss(X) = S.

2.3. Terms

Definition 2.19

Fix a set of term-formers. f, g, h will range over distinct term-formers.

Define (permissive nominal) terms by:

r, s, t, . . . ::= a | X | f(r, . . . , r) | [a]r

We quotient terms by α-equivalence, where [a]r binds a in r and we treat X as a(n infinite) tuple. We may assume tupling term-formers and write (r1, r2) or (r1, . . . , rn).

Remark 2.20

The X in Definition 2.19 corresponds to a moderated unknown π·X from [38] or [11]. Whereas in [38] we ‘pick’ a set of unknowns and then attach permutations to them, in this paper we take the moderated unknowns as primitive. See [24] for a sorted permissive-nominal syntax.

Remark 2.21

Terms can be represented using standard methods.

We can use our favourite representation of syntax-with-binding in Definition 2.19: graphs to capture sharing; de Bruijn indexes; equivalence classes of α-equivalent terms; or nominal abstract syntax as introduced in the author’s thesis [18] and subsequent work [30, 22].

This author is ‘secretly’ using nominal abstract syntax but the reader need not do the same.

Remark 2.22

Terms are finite.

Terms are conceptually infinite structures (because the conceptual model of unknowns is infinite tuples), but finite representations are easily constructed—see Subsection 2.2.

Infinities like this are familiar and routinely taken for granted: examples include ‘1/3’ (whose decimal representation is infinite but which has a compact representation as . . . 1/3), ‘the number π’, ‘the α-equivalence class of the λ-term λx.x’, and ‘the set of natural numbers’.

Definition 2.23

We define free atoms fa(r) and a permutation action π·r by:

fa(a) = {a} fa(f(r1, . . . , rn)) = ⋃1≤i≤n fa(ri)fa([a]r) = fa(r)\{a} fa(X) = pmss(X)π·a = π(a) π·f(r1, . . . , rn) = f(π·r1, . . . , π·rn)π·[a]r = [π(a)]π·r π·X = (i↦ →π(xi))i≤0

Note the ‘pointwise’ nature of the clauses for fa(X) and π·X. An unknown X can be split up into ‘a π and a ϖ’ (see Lemma 2.16). This mirrors the moderated unknowns used in [38, 11].

Remark 2.24

If X = π′ ◦f ◦ϖ then π·X = (π ◦π′) ◦f ◦ϖ.

Lemma 2.25

• [a]r = [b]s if and only if b ∉ fa(r) and (b a)·r = s.

• [a]r = [b]s if and only if for fresh c (so c∉fa(r)∪fa(s)) (c a)·r = (c b)·s.

Proof

By elementary calculations. (If we use nominal abstract syntax to build our nominal terms then these two characteristic equalities are, in essence, a definition of α-equivalence by construction. Otherwise, they are well-known lemmas [30, 22].)End of proof

Lemma 2.26

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

Proof

Routine induction on r.End of proof

Lemma 2.27

If π(a) = π′(a) for all a ∈ fa(r) then π·r = π′·r.

Proof

First, we α-convert all bound atoms to be fresh for nontriv(π) ∪ nontriv(π′); as noted in Remark 2.6 we can always do this. We then argue by induction on the size of r. We consider two cases:

• The case of X. It is a structural fact of the pointwise permutation acting X (Definition 2.23) that if π(a) = π′(a) for all a ∈ fa(X) then π(a) = π′(a) for all a appearing in X considered as a tuple, and so π·X = π′·X.

• The case of [a]r′. From part 2 of Lemma 2.25, given that we α-converted all bound atoms to be fresh for the permutations.End of proof

2.4. Free unknowns of a term

Remark 2.28

Defining a notion of ‘the free unknowns of r’ is not entirely evident.

Consider for example [a]X where a ∈ pmss(X). If ‘X appears in [a]X’ is true then so is ‘(b a)·X appears in [a]X’ for any b ∉ pmss(X), since [a]X = [b](b a)·X. We deal with this in Definition 2.29 by quotienting up to all permutations. We take a more refined look at this later in Remark 2.58.

Definition 2.29

Define free unknowns fv(r) by:

fv(a) = ∅ fv(f(r1, . . . , rn)) = fv(r1) ∪· · · ∪fv(rn)fv([a]r) = fv(r) fv(X) = {orb(X)}

By abuse of notation we write X ∈ fv(r) for orb(X) ∈ fv(r) and X ∉ fv(r) for orb(X) ∉ fv(r), and so forth.

Remark 2.30

fv(r) may be computed as outlined in Corollary 2.17; intuitively, we just traverse the term and collect the ϖ (orb(X) in the clause for fv(X); see Definition 2.12).

Lemma 2.31

fv(r) is well-defined.

Proof

From Lemma 2.25 it suffices to prove that fv((b a)·r) = fv(r). This follows using Lemma 2.16.End of proof

2.5. Substitutions

Definition 2.32

A substitution θ is a function from unknowns to terms such that

∀π, X. θ(π·X) = π·θ(X).

We call θ equivariant. θ will range over substitutions.

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

The reader familiar with nominal terms will expect a ‘freshness’ condition on substitutions corresponding to ‘∇′ ⊢∇θ’, as in for example Equation (11) or Lemma 2.14 of [38], or ‘fa(θ(X)) ⊆ pmss(X)’ as in Definition 3.1 of [11]. In the context of this paper, that condition follows as a corollary of equivariance:

Lemma 2.33

If θ is a substitution then fa(θ(X)) ⊆ pmss(X) for all unknowns.

Proof

Suppose there exists a ∈ fa(θ(X)) \ pmss(X). Choose fresh b (so b ∉ fa(θ(X)) ∪ pmss(X)). Lemma 2.26 implies that (b a)·θ(X) ≠ θ(X). Yet since a, b ∉ pmss(X) also (b a)·X = X. Thus θ(X) ≠ (b a)·θ(X) = θ((b a)·X) = θ(X), a contradiction.End of proof

Definition 2.34

Suppose fa(t) ⊆ pmss(X). Write [X:=t] for the substitution such that

[X:=t](π·X) = π·t and [X:=t](Y ) = Y for all other Y.

Definition 2.34 is a special case of Definition 5.10. However, this case is of particular interest, and simpler, so it seems seems useful (and perhaps kinder to the reader) to consider it separately.

Remark 2.35

Unknowns from (permissive) nominal terms correspond to representatives of permutation equivalence classes.

In this paper both X and π·X are ω-tuples of atoms with equal standing in an equivalence class of unknowns of the form {π′·X | π′ a permutation}.3

When we specify [X:=t] we have chosen a particular representative X. To specify the action of [X:=t] on all unknowns we must consider unknowns in the permutation equivalence class of X, and unknowns not in this equivalence class. By part 1 of Lemma 2.16 the two cases of Definition 2.34 cover both possibilities and do not overlap.

The ‘moderated unknown’ π·X in Definition 2.34 is an artefact of our writing [X:=t] instead of a mathematically equal [π·X:=π·t] for some other π.

Since θ is constrained to be equivariant its behaviour on π·X is already determined by its behaviour on X and so we could unambiguously specify [X:=t] succinctly just as [X:=t](X) = t and [X:=t](Y ) = Y , or even (being just a little lax) just as [X:=t](X) = t.

Definition 2.36

Define a substitution action on terms by:

aθ = a f(r1, . . . , rn)θ = f(r1θ, . . . , rnθ)([a]r)θ = [a](rθ) Xθ = θ(X)

Note that Xθ refers to θ acting on X as a term whereas θ(X) refers the value of the function θ at X.

Lemma 2.37

π·(rθ) = (π·r)θ.

Proof

By a routine induction on r using equivariance.End of proof

Lemma 2.38

fa(rθ) ⊆ fa(r).

Proof

By induction on r using Lemma 2.33.End of proof

Lemma 2.39

rθ is well-defined.

Proof

The non-trivial part is to show that if [a]r = [b]s then ([a]r)θ = ([b]s)θ. Suppose [a]r = [b]s. By Lemma 2.25 b ∉ fa(r) and (b a)·r = s. By Lemma 2.38 b ∉ fa(rθ). By Lemma 2.37 (b a)·(rθ) = ((b a)·r)θ = sθ. We use Lemma 2.25 again.End of proof

Lemma 2.40

If θ(X) = θ′(X) for all X ∈ fv(r) then rθ = rθ′.

2.6. shift-permutation

Remark 2.41

The reader may be familiar with the de Bruijn shift function ↑ [1, Subsection 2.2]. This maps ℕ to ℕ \ {0} by mapping j ∈ℕ to j + 1 ∈ℕ, and in doing so it ‘creates a fresh number’ 0. The reader familiar with presheaf techniques may know of a functor δ and arrow up, which work the same way, as exemplified in [17, Section 1].

δ from Definition 2.4 follows the same general idea and does the same kind of job. It shifts ‘down’ instead of ‘up’, but δ-1 shifts ‘up’. Note that unlike ↑ and up, δ is invertible, consistent with the general preference of nominal techniques for using permutations on atoms.

All permission sets can be bijected with one another by a permutation. In particular, for every permission set S and atom a there exists some π such that S \ {a} = π·S. See Corollary 2.52. This would not be the case if we only admitted finite permutations. We use this in rule (IF) of Figure 1 to eliminate an atom from the support of an unknown.

Remark 2.42

The algorithm from [11, Section 6] used a notion of the ‘known unknowns’ V to do the job of δ. This introduced a notion of state and sequentiality into the algorithm. The original algorithm from [38] also avoided sequentiality, by using freshness constraints a#t.

Very broadly speaking, the reader can translate ‘a#t’ in [38] to δ; the use of δ in the unification algorithm of Section 3, parallels the use of a#t in [38].

Notation 2.43

Recall the bijection f from integers to atoms from Definition 2.3. By abuse of notation write 0 for the atom f(0).

Definition 2.44

1. If a ∈𝔸< then define δ-a by:

δ-a = (a 0) ◦δ ◦(a 0)

2. If b ∈𝔸> then for some fixed but arbitrary choice of c ∈𝔸> such that δ(c) = c (and so also c ∉𝔸<), define δ+b by:

δ+b = (b 0) ◦(c b) ◦δ-1 ◦(c b) ◦(b 0)
Example 2.45

We illustrate δ-a and δ+b where a = f(-2) and b = f(3) and where we take c = b:

f(-6) f(-5) f(-4) f(-3) f(-2)f(-1) f(0) f(1) f(2) f(5) f(4) f(5) f(6) f(7)f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6) f(7)

We also consider the slightly more complex example of δ+d where d = f(4), and again we take c = f(3). We do this in three steps, where we illustrate δ-1, then (c d) ◦δ-1 ◦ (c d), and finally δ+d:

f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6) f(7)f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6) f(7)f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6) f(7)
Lemma 2.46

1. If a ∈𝔸< then δ-a bijects 𝔸< with 𝔸< \ {a}.

2. If b ∈𝔸> then δ+b bijects 𝔸< with 𝔸< ∪{b}.

Proof

For the first part, suppose a ∈𝔸<. Then 𝔸< = (a 0)·𝔸<. We reason as follows:

δ-a·((a 0)·𝔸<) = ((a 0) ◦δ ◦(a 0) ◦(a 0))·𝔸< = ((a 0) ◦δ)·𝔸< = (a 0)·(𝔸<\{0}) = 𝔸<\{a}

Now suppose b ∈𝔸>. It is easier to work with (δ+b)-1, to keep the parallel with the previous case. So 𝔸< ∪{b} = ((b 0)·𝔸<) ∪{0}. We reason as follows:

(δ+b)-1·(((b 0)·𝔸<)∪{0}) = ((b 0) ◦(c b) ◦δ ◦(c b) ◦(b 0))·(((b 0)·𝔸<) ∪{0}) (Def. 2.44) =(((b 0) ◦(c b) ◦δ ◦(c b) ◦(b 0))·((b 0)·𝔸<))∪{0} (δ(c)=c)=(((b 0) ◦(c b) ◦δ ◦(c b))·𝔸<)∪{0} (Fact)=(((b 0) ◦(c b) ◦δ)·𝔸<)∪{0} (b, c ∉𝔸<)=(((b 0) ◦(c b))·(𝔸<\{0}))∪{0} (δ·𝔸<=𝔸<\{0})= (𝔸<\{0}) ∪{0} (b, c ∉𝔸<\{0})= 𝔸<End of proof

Recall from Definition 2.10 that each permission set S has the form π·𝔸< for some permutation π.

Definition 2.47

For each S make some choice of permutation πS such that S = π-1 S ·𝔸<.4

Definition 2.48

Suppose S is a permission set and a ∈S and b ∉S. Then we define:

δS-a = π-1 S ◦δ-πS(a) ◦πSδS+b = π-1 S ◦δ+πS(b) ◦πS

The concrete details of the construction are only interesting insofar as they give us Lemma 2.49. Other permutations are possible, but we only need that one exists.

Lemma 2.49

1. δS-a bijects S with S\{a}.

2. δS+b bijects S with S∪{b}.

Proof

From Lemma 2.46.End of proof

Definition 2.50

Suppose S is a permission set and pmss(X) = S. Suppose D is a finite list of atoms d1, . . . , dn and E is a finite list of atoms e1, . . . , en. Suppose {d1, . . . , dn} ⊆S and {e1, . . . , en} ∩S = ∅. Then define δS-D and δS+E, and X-D and X+E by:

δS-[] = id δS-[d] = δS-dδS-d,D = δ(S\{d})-D ◦δS-dX-D = δpmss(X)-D·XδS+[] = id δS+[e] = δS+eδS+e,E = δ(S∪{e})+E ◦δS+eX+E = δpmss(X)+E·X
Lemma 2.51

Suppose S is a permission set. Suppose D and E are finite lists of atoms d1, . . . , dn and e1, . . . , en. Suppose {d1, . . . , dn} ⊆S and {e1, . . . , en} ∩S = ∅.

Then δS-D bijects S with S \ {d1, . . . , dn} and δS+E bijects S with S ∪{e1, . . . , en}.

Proof

Using Lemma 2.49.End of proof

Corollary 2.52

S is a permission set if and only if S = (𝔸<\A)∪B for some finite A ⊆𝔸< and B ⊆𝔸>.

Proof

If S is a permission set then by Definition 2.10 S = π·𝔸< for some π and the result follows by a routine induction on the generators of π (swapping and δ; see Definition 2.7).

Conversely consider S = (𝔸<\A)∪B. Let D be the atoms in A in some order, and E be the atoms in B in some order. Then we apply δS-D and then δ(S\A)+E and use Lemma 2.51.End of proof

2.7. Invertible substitutions

In this brief subsection we discuss some simple constructions which will be useful later.

Definition 2.53

Define composition of substitutions θ1◦θ2 by

(θ1◦θ2)(X) = (θ1(X))θ2.
Lemma 2.54

(rθ)θ′ = r(θ◦θ′).

Proof

By a routine induction on r, we consider one case.5

• The case X. We reason as follows:

X(θ◦θ′) = (θ◦θ′)(X) Definition 2.36= (θ(X))θ′Definition 2.53= (Xθ)θ′Definition 2.36End of proof
Definition 2.55

Call θ invertible when there exists θ-1 such that θ◦θ-1 = θ-1◦θ = id.

Lemma 2.56

θ is invertible if and only if θ is a bijection on the set of all unknowns. Furthermore, if θ is invertible then pmss(θ(X)) = pmss(X) always.

Proof

Substitution cannot make syntax smaller, or (by Lemma 2.38) make free atoms larger.End of proof

Proposition 2.57

Given any finite set of unknowns X there exists an invertible substitution θ such that for every X ∈X it is the case that orb(θ(X)) ∉{orb(X′) | X′ ∈X}.

Proof

Using Proposition 2.18.End of proof

So—just as for atoms—we can always rename unknowns to ‘be fresh’. The reader might note that we do not actually need θ to be invertible (it suffices for it to be injective on X). However, the invertible construction is no harder and is also a special case of a more abstract framework explored elsewhere [23].

2.8. Occurrences

Remark 2.58

As discussed in Remark 2.28 we have to be careful if we wish to say ‘X appears in r’; this might not quite mean what we think it does.

For example if ‘X appears in [a]X’ where a ∈ pmss(X) then also ‘(b a)·X appears in [a]X’ for any b ∉ pmss(X), since [a]X = [b](b a)·X.

We dealt with this in Definition 2.29 by quotienting out all permutations. But this is a little drastic.

For instance, ‘(b a)·X appears in [a]X’ is not true for b ∈ pmss(X); it is not the case that if ‘X appears in r’ then ‘π·X appears in r’ for any π.

We did not need to quotient out all permutations—only some of them—and so re-turning orb(X) in Definition 2.29 throws out more information than necessary.

Definitions 2.59 and 2.60 develop a more refined notion of occurrence, based on an intuition of ‘X appears in r under a list of abstractions D’. This will be useful later.

Definition 2.59

D will range over finite lists of distinct atoms. A (level 2) occurrence is a term of the form [D]X where []X is X and [a, D]X is [a][D]X.

Definition 2.60

Define the occurrences in r inductively by:

occ(a) = ∅ occ(X) = Xocc(f(r1, . . . , rn)) = ⋃ occ(ri) occ([a]r) = {[a, D]X | [D]X ∈occ(r), a ∉D}
Example 2.61

• X occurs in X.

• [a]X occurs in [a]X and also in [a](X, Y); so does [a]Y . X does not occur in [a]X or [a](X, Y).

• Suppose c is fresh (so c ∉𝔸<). Then [a][b]X and [a][c](c a)·X occur in [a]([b]X, [a]X). We quotient terms by α-equivalence, so [a][c](c a)·X is equal to [a][a]X and thus [a][a]X occurs in [a]([b]X, [a]X).

3. Permissive nominal unification

We now revisit material from nominal unification [38] and permissive-nominal unification [11]. The algorithm here is in the same spirit as this previous work, but there are significant differences:

• Solutions are equality constraints. Solutions to nominal unification problems from [38] include also freshness constraints a#r. Their job is done here by permission sets; this is inherited from the permissive-nominal algorithm in [11].

• Our algorithm does not keep track of a context of ‘known’ unknowns. The permissive-nominal unification algorithm in [11] needed to keep track of a context of ‘known’ unknowns written V; see for instance Figure 5 of [11]. The job of V is done here by δ. We find this gives easier proofs.

The main definition of this section is Definition 3.8. The main result is Theorem 3.25.

3.1. The unification algorithm

Definition 3.1

An equality is a unordered pair r?= s (so r?= s is identical to s?= r) such that:

1. sort(r) = sort(s).

2. If [D]X and [D′]π·X are both in occ(r) ∪ occ(s) then π is finite. So we exclude an equality like X?= δ·X, where δ is a shift permutation and nontriv(δ) ∩ pmss(X) is not finite.

A freshness is an ordered pair a#?r.

Let ef range over equalities or freshnesses and define ef θ by:

(r?= s)θ = (rθ?= sθ) (a#?r)θ = (a#?(rθ))

A unification problem Pr is a finite list ef1, . . . , efn.

We (ab)use standard sets notation and write ef ∈Pr as shorthand for ‘ef appears in the list Pr’.

Remark 3.2

Condition 2 in Definition 3.1 protects (?=X) in Figure 1 from an ‘infinite freshness explosion’, if nontriv(π)∩pmss(X) is not finite. This condition exists implicitly in [38], in the sense that all permutations there are finite. We discuss the implications of this condition to nominal rewriting, at the end of Section 5.

Definition 3.3

If Pr = ef1, . . . , efn is a problem then define Prθ by:

Prθ = ef1θ, . . . , efnθ

Say θ solves Pr when

rθ = sθ for every r?= s ∈Pr, anda ∉fa(rθ) for every a#?r ∈Pr.

Write Sol(Pr) for the set of solutions to Pr and call Pr solvable when Sol(Pr) is non-empty.

(?=a) a?= a, Pr =⇒ Pr(?=f) f(r1, . . .)?= f(s1, . . .), Pr =⇒ r1?= s1, . . . , Pr(?=[]) [a]r?= [a]s, Pr =⇒ r?= s, Pr(?=X) X?= π·X, Pr =⇒ a1#?X, . . . , an#?X, Pr ({a1, . . . , an} = nontriv(π) ∩supp(X))(F) r?= X, Pr =⇒ a#?r, r?=X, Pr (a ∈fa(r)\pmss(X))(F#) a#?r, Pr =⇒ Pr (a ∉fa(r))(Ff) a#?f(r1, . . . , rn), Pr =⇒ a#?r1, . . . , a#?rn, Pr(F[]) a#?[b]r, Pr =⇒ a#?r, Pr(IE) r?= X, Pr[X:=r]=⇒ Pr[X:=r] (X∉fv(r), fa(r)⊆pmss(X))(IF) a#?X, Pr[X:=δpmss(X)-a·X]=⇒ Pr[X:=δpmss(X)-a·X]
Figure 1: Simplification rules for problems
Lemma 3.4

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

Proof

By unpacking Definition 3.3 and using Lemma 2.54.End of proof

Definition 3.5

Define a simplification rewrite relation Pr =⇒Pr′ on unification problems by the rules in Figure 1.

We call rules (IF) and (IE) instantiating rules. We call all the other rules non-instantiating rules.

Write =⇒∗ for the transitive and reflexive closure of =⇒.

Remark 3.6

The instantiating rule (IF) preserves condition 2 of Definition 3.1 because it applies [X:=δpmss(X)-a·X] uniformly to all occurrences involving X. Condition 2 does not outlaw δ, it just outlaws attaching it to one occurrence of X and not another.

Remark 3.7

Unlike was the case in [38], there is no separate simplification rule for [a]r?= [b]s. This is because we have quotiented syntax by α-equivalence, so a and b can both be renamed to some fresh c. This was not possible in [38] because there, α-equivalence takes place in a freshness context (a set of freshness assumptions on unknowns) whereas here it does not (instead of freshness contexts we have permission sets, which are static and fixed).

A reader might be now be tempted to comment “so the syntax of [38] is lower-level than the syntax of this paper”. Not necessarily so. An implementation of nominal syntax might well seek a representation in which bound atoms really are nameless.

Definition 3.8

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

1. Rewrite Pr using the rules of Definition 3.5 where possible, with top-down precedence (so apply (?=a) before (?=f), and so on).

2. If we reduce to ∅ then we succeed and return θ where θ is the composition of all the substitutions labelling rewrites (we take θ = id if there are none). Otherwise, we fail.

Remark 3.9

In Definition 3.8, we apply each rule to the head of the list Pr. This is to prevent ‘unfair’ looping, e.g. repeatedly applying (F) to some equality r?= X wherever it appears in Pr.

We note in passing that the rule (F#) is equivalent—in the presence of the other rules—to a pair of rules a#?b, Pr =⇒Pr and a#?X, Pr =⇒Pr if a ∉ pmss(X).

Proposition 3.10

The algorithm of Definition 3.8 always terminates.

Proof

It is not hard to generate an inductive quantity which is reduced by the reductions in Figure 1.End of proof

Remark 3.11

In [33] it is suggested to implement freshness conditions in nominal unification using equality conditions of the form [a]r?= [b]s. Freshness can be approached using equality alone, as was also noted in Theorem 5.5 from [26] and Lemma 4.51 from [27]. In the context of nominal unification the observation of [33] is that doing so avoids having to ‘write algorithms twice’.

This technique is not so directly applicable here, because [a]r?= [b]s is identical to [c](c a)·r?= [c](c b)·s for fresh c, because we already quotiented by α-equivalence. This equality in turn has the same value as (c a)·r?= (c b)·s—technically, this happens via ([]?=).

This suggests that we might do something slightly different from [33] but in the same spirit, and also in the same spirit as Theorem 5.5 from [26]—which is no coincidence since both are related to the definition of freshness using the N-quantifier from [30]: we could encode a#?r as r?= (b a)·r for b ∉ pmss(r).

However, this would not really simplify our algorithm here. The design of (F) re-lies on generating freshness conditions which are then solved; if we lost freshness conditions then to avoid looping we would have to ‘hard-wire’ recognition of equality-constraints-that-are-really-freshness-conditions into the algorithm instead. The gain from doing this is not clear.

Freshness conditions on syntax really do seem to be independently useful. This is not absolute—we could eliminate them—but they ‘want’ to be there, and are natural in the algorithms.

3.2. Examples of the algorithm

Recall the definition of X-D from Definition 2.48.

Example one (succeeds).

Suppose a, c ∈𝔸< and d ∉𝔸<. Take pmss(X) = 𝔸< and suppose a term-former g. We apply the algorithm to {g([a]X, [a]a) ?= g([d]c, [d]d)}:

g([a]X, [a]a)?= g([d]c, [d]d) =⇒ (?=g), (?=())[a]X?= [d]c , [a]a?= [d]d =⇒ (?=[]), [a]X = [d](d a)·X(d a)·X?= c , [a]a?= [d]d[X:=c]=⇒ (IE)[a]a?= [d]d =⇒ (?=[]), [a]a = [d]dd?= d=⇒ (?=a)∅ Success, with [X:=c]

Example two (succeeds).

Suppose a, c ∈𝔸< and b, d ∉𝔸<. Take pmss(X) = 𝔸< ∪{b, d}, pmss(Y ) = 𝔸< ∪{b′}, and pmss(Z) = 𝔸<. Suppose a term-former f.

We apply the algorithm to {f([a]b, Z, X) ?= f([d]b, [a]a, Y)}:

f([a]b, Z, X)?= f([d]b, [a]a, Y ) =⇒ (?=f), (?=())[a]b?= [d]b , Z?= [a]a, X?= Y =⇒ (?=[]), [a]b = [d]bb?= b , Z?= [a]a, X?= Y =⇒ (?=a)Z?= [a]a , X?= Y[Z:=[a]a]=⇒ (IE)X?= Y=⇒ (F)b#?X , X?= Y[X:=X-b]=⇒ (IF)X-b?= Y=⇒ (F)d#?X-b , X-b?= Y[X-b:=X-b,d]=⇒ (IF)X-b, d?= Y =⇒ (F)b′#?Y , X-b, d?= Y[Y :=Y -b′]=⇒ (IF)X-b, d?= Y -b′[Y -b′:=X-b,d]=⇒ (IE)∅ Success, with [X:=X-b, d, Y :=X-b, d, Z:=[a]a]

Example three (fails).

Take pmss(X) = 𝔸<. We run the algorithm on {[a][b]X?= [a]X}:

[a][b]X?= [a]X =⇒ (?=[])[b]X?= X Failure

The algorithm fails because the precondition of rule (IE), X ∉ fv([b]X) is not satis-fied.

Example four (succeeds).

Take pmss(X) = 𝔸< and take a, b ∈𝔸<. We run the algorithm on {X?= (a b)·X}:

X?= (a b)·X =⇒ (?=X)a#?X , b#?X[X:=X-a]=⇒ (IF)b#?X-a[X-a:=(X-a)-b]=⇒∅ Success, with [X:=(X-a)-b]

Later we will prove Theorem 3.25, which tells us that failure here implies that no solution to the unification problem exists.

3.3. Preservation of solutions

3.3.1. ...under non-instantiating rules

Lemma 3.12

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

Proof

The empty set cannot be simplified, so suppose Pr = r?=s, Pr′ where the simplification rule acts on r?= s. We consider two cases:

• The case (?=[]). Suppose Pr = [a]r?=[a]s, Pr′ and [a]r?=[a]s, Pr′ =⇒r?=s, Pr′ by (?=[]). By Definition 2.36 and properties of equality, [a](rθ) = [a](sθ) if and only if rθ = sθ.

• The case (Ff). Suppose Pr = a#?f(r1, . . . , rn), Pr′ and a#?f(r1, . . . , rn), Pr′ =⇒ a#?r1, . . . , a#?rn, Pr′ by (Ff). By Definitions 2.36 and 2.23, a ∉ fa(f(r1, . . . , rn)θ) if and only if a ∉ fa(r1θ), ..., a ∉ fa(rnθ).

• The case (F). Suppose Pr = r?=X, Pr′ and a ∈ pmss(X)\fa(r), and r?=X, Pr′ =⇒ a#?r, r?=X, Pr′ by (F). Now if θ solves r?= X then θ(X) = rθ. By Lemma 2.38 fa(rθ) ⊆ pmss(X) and so in particular θ also solves a#?r. The result follows.End of proof

Lemma 3.13

rθ = rθ′ if and only if ∀X∈fv(r).θ(X) = θ′(X).

Proof

By a routine induction on r. We consider two cases:

• The case [a]r. Suppose θ(X) = θ′(X) for every X ∈ fv([a]r). fv([a]r) = fv(r) so by inductive hypothesis rθ = rθ′. The result follows from the definitions. The reverse implication is similar.

• The case X. Suppose θ(π·X) = θ′(π·X) for all π. Then taking π = id we have Xθ = θ(X) = θ′(X) = Xθ′. Conversely if Xθ = Xθ′ then by equivariance (Definition 2.32) θ(π·X) = θ′(π·X) for all π.End of proof

Remark 3.14

Recall from Definition 2.29 that we write X ∈ fv(r) for orb(X) ∈ fv(r). It may seem in Lemma 3.13 that the condition ∀X∈fv(r).θ(X) = θ′(X) would require checking θ(X) = θ′(X) for infinitely many X provided that fv(r) ≠ ∅. In fact, this is not the case: by equivariance of θ, we only need to check equality for finitely many representative X.

Lemma 3.15

Suppose θ(X) = θ′(X) for all X ∈ fv(Pr). Then θ ∈ Sol(Pr) if and only if θ′ ∈ Sol(Pr).

Proof

From Definition 3.3 it suffices to show that rθ = sθ if and only if rθ′ = sθ′, for every (r?= s) ∈Pr, and a ∉ fa(rθ) if and only if a ∉ fa(rθ′), for every (a#?r) ∈Pr. This is immediate using Lemma 3.13.End of proof

3.3.2. ...under (IE)

Recall from Remark 2.35 the discussion of why we write π·X when we have chosen a representative element X of an equivalence class of unknowns under permutations.

Definition 3.16

Write θ−X for the substitution such that

(θ−X)(π·X) = π·X and(θ−X)(Y ) = θ(Y ) for all other Y.

In the right circumstances, a substitution θ can be factored as ‘a part of θ that does not touch X’ and ‘a single substitution for X’:

Theorem 3.17

If Xθ = sθ and X ∉ fv(s) then θ = [X:=s]◦(θ−X). That is,

θ(X) = X([X:=s]◦(θ−X)) and θ(Y ) = Y ([X:=s]◦(θ−X)).
Proof

We reason as follows:

(π·X)([X:=s]◦(θ−X)) = (π·s)(θ−X) Definition 2.36, Lemma 2.54= (π·s)θ X∉fv(s), Lemma 3.13= (π·X)θ AssumptionY ([X:=s]◦(θ−X)) = Y (θ−X) Definition 2.36, Lemma 2.54= Y θ Definition 3.16End of proof

3.3.3. ...under (IF)

Definition 3.18

Suppose θ is a substitution. Suppose a ∈ pmss(X) and a ∉ fa(θ(X)). Define a substitution θ[X-a:=X](X) by:

• (θ[X-a:=X])(π·X) = (π ◦δ-1 X-a)·θ(X). • (θ[X-a:=X])(Y ) = θ(Y ) for all other Y .

It is routine to verify that Definition 3.18 is well-defined and a substitution.

Theorem 3.19

Suppose a ∈ pmss(X) and a ∉ fa(θ(X)). Then

θ(π·X) = ([X:=X-a]◦(θ[X-a:=X]))(π·X).
Proof

We unpack definitions:

([X:=X-a]◦(θ[X-a:=X]))(π·X) = (π·(X-a))θ[X-a:=X]Definition 2.53 = ((π◦δX-a)·X)θ[X-a:=X] Definition 2.50 = (π ◦δX-a ◦δ-1 X-a)·X Definition 3.18= π·X Fact of the group actionEnd of proof

3.4. Simplification rewrites calculate principal solutions

Definition 3.20

Write θ1 ≤θ2 when there exists some θ′ such that Xθ2 = X(θ1 ◦θ′) always. Call ≤ the instantiation ordering.

Definition 3.21

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

Our main result is Theorem 3.24: the unification algorithm from Definition 3.8 calculates a principal solution.

Lemma 3.22

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

Proof

By Definition 3.20, θ′ exists such that Xθ2 = X(θ1◦θ′) always. Then:

X(θ◦θ2) = (Xθ)θ2Lemma 2.54= (Xθ)(θ1◦θ′) Lemma 3.13= X((θ◦θ1)◦θ′) Lemma 2.54End of proof
Lemma 3.23

1. Suppose fa(s)⊆pmss(X) and X ∉ fv(s). Write χ=[X:=s]. If Prχ=⇒

Pr′ with (IE) then θ ∈Sol(Pr) implies θ−X ∈Sol(Pr′).

2. Suppose a ∈ pmss(X). Write ρ=[X:=X-a]. If Prρ=⇒Pr′ with (IF) then θ ∈ Sol(Pr) implies θ[X-a:=X] ∈ Sol(Pr′).

Proof

1. Suppose Pr = X?= s, Pr′′ so that X?= s, Pr′′χ=⇒Pr′′χ. Now suppose θ ∈ Sol(Pr). By Theorem 3.17 χ◦(θ−X) ∈ Sol(Pr). By Lemma 3.4, θ−X ∈ Sol(Prχ). It follows that θ−X ∈ Sol(Pr′′χ) as required.

2. Suppose Pr = a#?X, Pr′′ and a ∈ pmss(X) so that Prρ=⇒Prρ. Now suppose θ ∈ Sol(Pr). By Theorem 3.19 ρ◦θ[X-a:=X] ∈ Sol(Pr). By Lemma 3.4, θ[X-a:=X] ∈ Sol(Prρ) as required.End of proof

Theorem 3.24

If Prθ=⇒∗∅ then θ is a principal solution to Pr (Definition 3.21).

Proof

By induction on the path of Prθ=⇒∗∅.

• The empty path. So Pr = ∅ and θ = id. By Definition 3.20, id ≤θ′.

• The non-instantiating case. Suppose

Pr =⇒Pr′θ=⇒∗∅

where Pr =⇒Pr′ by a non-instantiating rule. By inductive hypothesis θ is a principal solution of Pr′. It follows from Lemma 3.12 that θ is also a principal solution of Pr.

• The case (IE). Suppose fa(r) ⊆ pmss(X) and X ∉ fv(r). Write χ = [X:=r]. Suppose Pr = r?=X, Pr′′ so that

r?=X, Pr′′χ=⇒Pr′′χθ′′=⇒∗∅.

Further, consider any other θ′ ∈ Sol(Pr). By Lemma 3.23 (θ′−X) ∈ Sol(Pr′′χ) and by inductive hypothesis θ′′ ∈ Sol(Pr′′χ) and θ′′ ≤θ′−X. By Lemma 3.22, χ◦θ′′ ≤χ◦(θ′−X). By Theorem 3.17 χ◦(θ′−X) = θ′.

• The case (IF). Suppose a ∈ pmss(X). Write ρ = [X:=X-a], so that

Prρ=⇒Prρθ′′=⇒∗∅,

Further, consider any other θ′ ∈ Sol(Pr). By Lemma 3.23, θ′ [X-a:=X] ∈ Sol(Prρ) and by inductive hypothesis θ′′ ∈ Sol(Prρ) and θ′′ ≤θ′ [X-a:=X]. By Lemma 3.22, ρ◦θ′′ ≤ρ◦θ′ [X-a:=X]. By Theorem 3.19 ρ◦θ′ [X-a:=X] = θ′.End of proof

Theorem 3.25

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

Proof

If the algorithm succeeds we use Theorem 3.24. Otherwise, the algorithm gener-ates 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#?a, or X?= s where X ∈ fv(s). By arguments on syntax and size of syntax, no solution to the reduced problem exists. It follows by Lemma 3.23 that no solution to Pr exists.End of proof

Definition 3.26

Fix terms r and s.

• Call nominal unification the problem of finding a θ to make rθ = sθ.

• Call nominal matching the problem of finding a θ to make rθ = s.

Corollary 3.27

Nominal unification and nominal matching are decidable.

Proof

An algorithm for unification is sketched in Definition 3.8; furthermore by Theorem 3.25 it calculates a most general θ which represents all other solutions.

For matching, by Proposition 2.57 we can invertibly substitute unknowns in r so they are disjoint from unknowns in s and run the unification algorithm with the mod-ification that it should not trigger (IE) or (IF) for X ∈ fv(r). It is not hard to see that this calculates a most general matching solution.End of proof

4. Rewriting

Nominal rewriting was introduced in [14, 12]. The use of nominal terms allows us to write rewrite rules for systems with binding, such as the λ-calculus (Example 4.2). The material from [12] simplifies (for completeness and to enable meaningful comparison, we sketch full proofs).

4.1. Rewriting, local confluence, confluence

Definition 4.1

A rewrite rule is a pair l →m such that fv(m) ⊆ fv(l). R will range over rewrite rules. A rewrite theory R is a (possibly infinite) set of rewrite rules.

The notion of rewrite rule and rewrite theory in Definition 4.1 is much like the first-order case, but because of the ‘nominal’ aspects of our syntax we can handle names and binding.

Example 4.2

We write down a signature and some rewrite rules for the untyped λ-calculus. Assume a name-sort ν and a base sort ι and term-formers lam : ([ν]ι)ι, app : (ι, ι)ι, and var : (ν)ι. Sugar lam([a]r) to λa.r and app(r′, r) to r′r and var(a) to a.

An axiom for η-reduction is:

λa.(Za) →Z (a ∉pmss(Z)) (η)

Here is that same η-equivalence axiom, written out as it would be informally:

λx.(tx) →t if x ∉fv(t)

The reader can see how similar they look written out on the page, but one is written in a formal syntax, and the other is not. Note how permission sets are used to avoid or permit capture.

If we sugar (λa.r)r′ to r[a↦→r′] then rewrites for β-reduction are:

a[a↦→Y ] →Y Z[a↦→X] →Z (a ∉pmss(Z))(X′X)[a↦→Y ] →(X′[a↦→Y ])(X[a↦→Y ]) (λa.X)[b↦→Z] →λa.(X[b↦→Z]) (a ∉pmss(Z))X[a↦→a] →X

There is no rule for the general case of Z[a↦→X] where a ∈ pmss(Z)—this does not reduce. Similarly in informal practice we cannot say anything about the reductions of the schema of terms represented by (λa.t)r without knowing any further particulars of what t and r range over. For more on this example and others like it, see Examples 5.1.3 and 7.1.3 of [24].6

We now set about defining the rewrites generated by a nominal rewrite theory.

Definition 4.3

Define the terms s in which X occurs only once by:

s ::= π·X | [a]s | f(r1, . . . , ri−1, s, ri+1, . . . , rn) (X ∉fv(r1), . . . , fv(ri−1), fv(ri+1), . . . , fv(rn))

A position C is a pair (s, X) of a nominal term and an unknown X which occurs only once in s.

Remark 4.4

In Definition 4.3, π·X denotes an unknown in the same permutation equivalence class as X. For example:

• X occurs only once in π·X.

• π·X occurs only once in X (recall that π·X is a well-ordering of π·pmss(X)).

• X and π·X do not occur in a Y such that orb(Y) ≠ orb(X).

Notation 4.5

If C = (s, X) is a position write pmss(C) for pmss(X).

If fa(r) ⊆ pmss(C) (so that [X:=r] is a substitution) write C[r] for s[X:=r].

Definition 4.6

The one-step rewrite relation rR−→s is the least relation such that for every (l →m) ∈ R, position C, and substitution θ, if fa(lθ) ∪ fa(mθ) ⊆ pmss(C) (so that C[lθ] and C[mθ] are well-defined) then

C[lθ]R−→C[mθ].

The multi-step rewrite relation rR→∗s is the reflexive transitive closure of the one-step rewrite relation.

Remark 4.7

Note that rR−→s implies π·rR−→π·s holds by construction because of the π·X in Definition 4.3.

Example 4.8

Recall the rule (η) from Example 4.2: λa.(Za) →Z where a ∉ pmss(Z).

• To deduce λa.(ba) →b where b ∉ pmss(Z) we take C = ((b c)·Z, Z) for some c ∈ pmss(Z) and we take θ = [Z:=c].

• To deduce λa′.(ba′) →b we also take C = ((b c)·Z, Z) and θ = [Z:=c]. This is because λa′.(ba′) and λa.(ba) are α-equivalent and we (use nominal abstract syntax or) quotient syntax by α-equivalence.

• To deduce λa.(Za) →Z we take C = (Z, Z) and θ = id.

• Suppose pmss(Z′) = pmss(Z) ∪{a}. To deduce λa.(Z′a) →Z′ we take C = ((δZ′-a)-1·Z, Z) and θ = [Z:=δZ′-a·Z′].

• We cannot deduce λa.(aa) →a, because [Z:=a] is not a substitution: no function mapping Z to a can be equivariant, since (b a)·Z = Z but (b a)·a = b ≠ a (also a ∉ pmss(Z): see Lemma 2.33).

Some terminology will be useful later, so we introduce it now in one place:

Definition 4.9

• Call R locally confluent when rR−→s1 and rR−→s2 implies there exists some s′ such that s1R→∗s′ and s2R→∗s′.

• Call R confluent when rR→∗s1 and rR→∗s2 implies there exists some s′ such that s1R→∗s′ and s2R→∗s′.

We illustrate this below.

rs1∗s2∗s′r∗∗s1∗s2∗s′rs1s2s′Local confluence Confluence Strong confluence

4.2. Peaks, critical pairs, joinability

We now investigate criteria for deducing confluence of nominal rewrite systems.

Definition 4.10

Consider two rewrite rules R1 = (l1 →m1) and R2 = (l2 →m2). Call R1 a copy of R2 when there exists an invertible substitution θ (Definition 2.55) such that (l2θ →m2θ) = R1.

Clearly, if R1 is a copy of R2 then R2 is also a copy of R1. Furthermore:

Lemma 4.11

If R1 and R2 are copies of the same rule then lR1−→m if and only if lR2−→m.

Proof

Unpacking Definition 4.6 and exploiting the existence of an inverse θ-1.End of proof

Definition 4.12

Write r →s1, s2 when r →s1 and r →s2 and call this a peak. Call this peak joinable when there exists a t such that s1 →∗t and s2 →∗t.

So R is locally confluent when every peak is joinable.

Definition 4.13

Suppose that Ri = (li →mi) for i = 1, 2 and fv(R1) ∩ fv(R2) = ∅. Suppose l1 = L[l′ 1] for some l′ 1 and l′ 1?= l2 has a principal solution θ. Call the pair (m1θ, L[m2]θ) a critical pair.

Call (m1θ, L[m2]θ) trivial when at least one of the following hold:

1. L = (π·X, X) and R1 and R2 are copies of the same rule.

2. l′ 1 = X for some unknown X.

Lemma 4.14

Peaks that are instances of trivial critical pairs, are not always joinable.

Proof

It suffices to provide a counterexample. Fix term-formers 0 and f and take R1 = (0 →a) and R2 = (X → f(a)) where a ∉ pmss(X).

There is a critical pair (a, f(a)) between R1 and R2.

Also, 0 R1−→a and 0 R2−→ f(a) and it is a fact that this peak cannot be joined—we ‘want’ to close this peak by rewriting a to f(a) using R2, but the fact that a ∉ pmss(X) blocks this.End of proof

Remark 4.15

In nominal rewriting from [12] it was not in general the case that if ∆⊢ r ≈α r′ and ∆⊢rR−→s then ∆⊢r′R−→s (see the end of Subsection 5.2 in [12]).

That has become irrelevant in this paper, because of our different treatment of α-equivalence.

The subtle point here is not that we quotient by α-equivalence, though we do; but that we can quotient by α-equivalence. Conversely, the point about [12] is not that we did not quotient; it was that we could not quotient, as reflected by the fact that rewriting did not respect α-equivalence.

The notion of rewriting of this paper corresponds more closely to rewriting in an arbitrarily extended freshness context, as developed in [13]; see for example Theorem 4.4 of [13].

4.3. Uniform rewriting

Definition 4.16

Call a rule R = (l →m) uniform when fa(m) ⊆ fa(l). Call a rewrite theory R uniform when every R ∈ R is uniform.

Definition 4.16 mirrors the condition in Definition 4.1 that fv(m) ⊆ fv(l), but for atoms instead of unknowns.

Lemma 4.17

If fa(m) ⊆ fa(l) then fa(C[m]) ⊆ fa(C[l]).

Proof

Routine induction using Lemma 2.26 and Definition 2.23.End of proof

Corollary 4.18

R = (l →m) is uniform if and only if ∀r,s.rR−→s ⇒ fa(s) ⊆ fa(r).

Proof

From Lemmas 2.26 and 2.38.End of proof

Lemma 4.19

Suppose R = (l →m) is uniform and X ∉ fv(R). Suppose θ(X) = lθ. Specify θ′ by θ′(π·X) = π·(mθ) and θ′(Y ) = θ(Y). Then rθ →∗rθ′ for any r.

Proof

θ′ is a substitution by Lemmas 2.38 and 2.26. The result follows by a routine induction on r.End of proof

Theorem 4.20

If a rewrite theory R (Definition 4.1) is uniform then peaks that are instances of trivial critical pairs, are joinable.

Proof

Consider two rules Ri = (li →mi) ∈ R for i = 1, 2. Without loss of generality we suppose the unknowns of R1 are disjoint from those of R2. Suppose they have a critical pair (m1θ, L[m2]θ). That is, there exists l′ 1 such that l1 = L[l′ 1] and θ is a principal solution to l′ 1?= l2.

There are two cases:

• The case L = (π·X, X) and R1 and R2 are copies of the same rule l →m. The peak we want to join is l1θ = π·l2θ →m1θ, π·m2θ, where the rules l1 →m1 and l2 →m2 are identical aside from their free variables which are renamed disjoint. We use Lemma 3.13 and the assumption in Definition 4.1 that fv(m) ⊆ fv(l).

• The case L = (m1θ, L[m2]θ) where l1 = L[X] and θ(X) = l2. Specify θ′ by θ′(π·X) = π·m2 and θ′(Y ) = θ(Y) for all other Y ; note that θ′ is a substitution since fa(m2) ⊆ fa(l2) by uniformity and fa(l2) ⊆ pmss(X) by our assumption that θ is a substitution. By Lemma 4.19 m1θ →m1θ′. By definition L[m2]θ = l1θ′R1−→m1θ′, so we have joined the peak.End of proof

Theorem 4.21

Suppose R is uniform and all non-trivial critical pairs of R are joinable. Then R is locally confluent.

Proof

Suppose rR1−→s1 and rR2−→s2. Write L1 and L2 for the positions at which the two rewrites occur.

If L1 and L2 identify distinct subterms of r then local confluence holds by a standard diagrammatic argument (see for instance [2]).

Otherwise it must be that L2 = (L1[L], X); that is, L2 identifies a point in r beneath the point identified by L1 (or the symmetric case that L1 = (L2[L], X), which is similar and we elide). There are now three possibilities:

1. X in L2 replaces an unknown in r. This is an instance of a trivial critical pair; we use Theorem 4.20.

2. L = (π·X, X) and R1 and R2 are copies of the same rule. Then again this is an instance of a trivial critical pair and we use Theorem 4.20.

3. Otherwise, this is an instance of a non-trivial critical pair at it may be joined using our assumption that non-trivial critical pairs are joinable.End of proof

4.4. Terminating rewrite systems

Definition 4.22

Call a rewrite system R terminating when all rewrite sequences are finite. Call a term r a normal form (with respect to a rewrite system R) when ∀s.¬(rR−→ s), that is, when r does not R-rewrite to anything.

Corollary 4.23

Suppose R is terminating, uniform, and suppose non-trivial critical pairs in R are joinable. Then:

1. R is confluent.

2. If r →∗s and r →∗s′ and s and s′ are normal forms, then s = s′.

4.5. Orthogonal rewrite systems

Definition 4.24

Call R = (l →m) left-linear when each unknown occurring in l occurs only once (Definition 4.3).

For example f(X) → g(X, X) is left-linear but g(X, X) → f(X) and g(π·X, X) → f(X) are not. Note that (a, a) →a is left-linear.

Definition 4.25

Call R orthogonal when every R ∈ R is uniform and left-linear, and all critical pairs are trivial.

Definition 4.26

Suppose R = (l →m). Write rR→ϵ s when rR−→s and the rewrite occurs at a position C = (π·X, X). We say that the rewrite with R occurs at root position.

r1 ⇒s1 · · · rn ⇒sn(⇒f)f(r1, . . . , rn) ⇒f(s1, . . . , sn)r1 ⇒s1 · · · rn ⇒snf(s1, . . . , sn)R→ϵ s′(⇒f′)f(r1, . . . , rn) ⇒s′s ⇒t(⇒abs)[a]s ⇒[a]tr ⇒s [a]sR→ϵ s′(⇒abs′)[a]r ⇒s′(refl)r ⇒raR→ϵ s′(⇒a′)a ⇒s′XR→ϵ s′(⇒X′)X ⇒s′
Figure 2: Parallel reduction relation

Expanding Definition 4.26, rR→ϵ s when there exists θ and π such that r = π·(lθ) and s = π·(mθ). For example: if R = (a →a) then aR→ϵ a but not [a]aR→ϵ [a]a.

We now set about proving Theorem 4.29, that → is confluent. Our proof-method, which is standard and goes back to [35], uses a parallel reduction relation ⇒ (Definition 4.27). We prove ⇒ confluent (Lemma 4.28) and then note that →∗=⇒∗. The reason we use ⇒ is because substitutions can turn ‘one rewrite’ into ‘many parallel rewrites’; see the diagram in Lemma 4.28.

Definition 4.27

We define a parallel reduction relation ⇒ by the rules in Figure 2.

Lemma 4.28

If R is orthogonal then ⇒ is strongly confluent (Definition 4.9), and therefore confluent.

Proof

We prove by induction on the derivation of r ⇒s that for all s′ if r ⇒s′ then there exists some s′′ such that s ⇒s′′ and s′ ⇒s′′. We consider a selection of cases:

• The derivations of r ⇒s and r ⇒s′ both end in (⇒f). We use the inductive hy-potheses and (⇒f).

• The derivation of r ⇒s ends in (⇒f) and that of r ⇒s′ ends in (⇒f′). So ri ⇒si and ri ⇒s′ i for 1 ≤i ≤n, and f(s′ 1, . . . , s′ n) = π·(lθ) R→ϵ π·(mθ) for some π and R = (l →m) ∈ R. By inductive hypothesis there exist s′′ i such that si ⇒s′′ i and s′ i ⇒s′′ i. We now proceed as illustrated and explained below:

f(r1, . . . , rn) f(s′ 1, . . . , s′ n)=π·(lθ)Rϵπ·(mθ)Many parallel rewritesf(s1, . . . , sn)f(s′′ 1, . . . , s′′ n)= π·(lθ′)Rϵπ·(mθ′)

Either l is an unknown X or the rewrite f(s′ 1, . . . , s′ n) ⇒ f(s′′ 1, . . . , s′′ n) takes place in the substitution θ. If l is an unknown then by uniformity we may rewrite f(s′′ 1, . . . , s′′ n) using R and close the diagram by rewriting corresponding instances of θ(X) in π·(mθ). Otherwise, by uniformity there is a substitution θ′ such that θ(X) ⇒θ′(X) for every X and f(s′′ 1, . . . , s′′ n) = π·(lθ′). Rules are also left-linear so R still applies to π·(lθ): f(s′′ 1, . . . , s′′ n) R→ϵ π·(mθ′) and therefore f(s1, . . . , sn) ⇒sθ′ by (⇒f′) for R. The other cases are no harder.End of proof

Theorem 4.29

If a theory R is orthogonal (Definition 4.25) then R is confluent (Definition 4.9).

Proof

If the uniform rewrite system has only left-linear rules and only trivial critical pairs, then ⇒ is confluent by Lemma 4.28. It is not hard to verify that →∗=⇒∗, and the result follows.End of proof

5. Closed terms

Equivariant unification—the problem of finding θ and π such that π·(rθ) = sθ—is NP complete [5]. The same applies to corresponding matching problems. This matters to us because the rewrite relation in Definition 4.6 is equivariant; to determine whether r rewrites with a rule (l →r), we must solve an equivariant matching problem.

Fernández and the author introduced a notion of closed term such that for closed terms, equivariant matching/unification coincides with ‘ordinary’ matching/unification [12]. That is, for closed terms we can throw away the π.

We now develop corresponding definitions and results. The definitions and proofs in this paper are significantly different from previous work.7

5.1. Closed terms, and the equivariant extension

Definition 5.1

Define explicit atoms ea(r) inductively by:

ea(a) = {a} ea(X) = ∅ ea(f(r1, . . . , rn)) = ⋃ ea(ri) ea([a]r) = ea(r)\{a}
Remark 5.2

The explicit atoms of r are the atoms that actually appear (unbound) in r. Contrast this with fa(r) which is intuitively the atoms that might appear in r (perhaps after a substitution). For instance, ea(X) = ∅≠ pmss(X) = fa(X).

Recall the notion of the occurrences in r from Subsection 2.8.

Notation 5.3

Write π·occ(r) = {π·[D]X | [D]X ∈ occ(r)}. Also if D = [d1, . . . , dn] and S is a permission set define S \ D = S \ {d1, . . . , dn}.

Lemma 5.4

ea(π·r) = π·ea(r) and occ(π·r) = π·occ(r). In addition, ea(r) ⊆ ea(rθ).

Proof

By routine inductions on r.End of proof

Lemma 5.5

fa(r) = ea(r) ∪⋃{fa([D]X) | [D]X ∈ occ(r)}.

Unpacking Definition 2.23, fa(r) = ea(r) ∪⋃{pmss(X) \ D | [D]X ∈ occ(r)}.

Definition 5.6

Call occ(r) fa-functional when if [D1]X ∈ occ(r) and [D2]X ∈ occ(r) then fa([D1]X) = fa([D2]X) (equivalently, when D1 and D2 contain the same atoms but not necessarily in the same order).

Definition 5.7

Call r closed when r is fa-functional and ea(r) = ∅.

Example 5.8

• a is not closed (ea is non-empty).

• X is closed.

• ([a]X, X) is not closed (occ is not fa-functional).

• [a](X, a) is closed.

Lemma 5.9

Suppose ea(r) = ∅. Then π·(rθ) = rθ′ if and only if π·(([D]X)θ) = ([D]X)θ′ for every [D]X ∈ occ(r).

Proof

By a routine induction on r (actually a nominal induction, since we α-convert). We consider some cases:

• The case X. By definition occ(X) = {X}. The result is immediate.

• The case a. ea(a) ≠ ∅ so there is nothing to prove.

• The case [a]r. α-renaming if necessary, suppose π(a) = a. By definition occ([a]r) = {[a, D]X | [D]X ∈ occ(r)}. Suppose π·(([a]r)θ) = ([a]r)θ′, so that from Definitions 2.23 and 2.36 and by Lemma 2.25, π·(rθ) = rθ′. By inductive hypothesis π·(([D]X)θ) = ([D]X)θ′. It follows that π·(([a, D]X)θ) = ([a, D]X)θ′. The reverse implication is similar.End of proof

We need Definition 5.10 and Proposition 5.11 for Theorem 5.12.

Definition 5.10

Suppose we are given the following data:

• For each ϖ (Definition 2.15) a fixed but arbitrary choice of representative Xϖ such that orb(X) = ϖ.

• For each Xϖ a choice of term rϖ such that fa(rϖ) ⊆ supp(Xϖ).

Define the equivariant extension F of this data by:

F(π·Xϖ) = π·rϖ
Proposition 5.11

1. The equivariant extension from Definition 5.10 is well-defined and is a substitution.

2. Every substitution θ is an equivariant extension.

Proof

For the first part, suppose π·Xϖ = π′·Xϖ. By construction that π(a) = π′(a) for every a ∈ supp(Xϖ). By assumption fa(rϖ) ⊆ pmss(Xϖ). The result follows by Lemma 2.27.

The second part is easy, noting that supp(θ(X)) ⊆ pmss(X) by Lemma 2.33.End of proof

Theorem 5.12

r is closed if and only if

∃S.fa(r) ⊆S ∧∀π, θ.π·fa(rθ) ⊆S ⇒∃θ′.π·(rθ) = rθ′.
Proof

Suppose there is a permission set S ⊇ fa(r) such that if π·fa(rθ) ⊆S then there exists θ′ such that π·(rθ) = rθ′. There are two things to prove:

• ea(r) is empty. Suppose there exists a ∈ ea(r). Pick b ∈S \ ea(r). By assumption taking θ = id there exists θ′ such that (b a)·(rθ) = rθ′. By Lemma 5.4 ea((b a)·r) = (b a)·ea(r) ∌a and a ∈ ea(r) ⊆ ea(rθ′), a contradiction.

• occ(r) is fa-functional. Consider [D1]X and [D2]X in occ(r); choose Di such that Di ∩ fa(r) = ∅ for i = 1, 2. Suppose there exists a ∈ fa([D2]X) \ fa([D1]X), and choose any b ∈ fa([D1]X) (since pmss(X) is infinite and D1 is finite, such a b exists). By Lemma 5.5 a, b ∈ fa(r) so by assumption taking θ = id there exists θ′ such that (b a)·r = rθ′. By Lemma 5.9 (b a)·[D1]X = ([D1]X)θ. By Lemma 2.26 a is free in the left-hand side, and by Lemma 2.38 a is not free in the right-hand side; a contradiction.

Suppose occ(r) is fa-functional and ea(r) = ∅ and choose some permutation π and substitution θ.

If occ(r) = ∅ then by Lemma 5.5 fa(r) = ∅ so by Lemmas 2.27 and 2.40 π·(rθ) = r and rθ′ = r, so there is nothing to prove.

Otherwise take S = fa(r). For every element of occ(r) make a fixed but arbitrary choice of representation as [D]X where the atoms in D are disjoint from the atoms in nontriv(π). We take θ′ to equivariantly extend this choice (Definition 5.10), so we map π′·X to (π′ ◦π)·θ(X) for the choice of representing X above, and otherwise to map Y to Y . Using Proposition 5.11 this is a substitution and π·(([D]X)θ) = ([D]X)θ′ for every [D]X ∈ occ(r). We use Lemma 5.9.End of proof

5.2. Closed rewrite rules

Definition 5.13

Call a rewrite rule l →m closed when (l, m) is closed.

Recall that uniform rules satisfy Theorems 4.29 and 4.21.

Theorem 5.14

If R = (l →m) is closed then it is uniform.

Proof

By assumption fv(m) ⊆ fv(l). Also (l, m) is fa-functional; it follows that occ(m) ⊆ occ(l). The result follows from Lemma 5.5.End of proof

Lemma 5.15

If fa(r) is infinite then fa(r) is a permission set.

Proof

By a routine induction on the definition of fa(r) in Definition 2.23, using Corollary 2.52.End of proof

Lemma 5.16

For any terms r and l, if there exists a π such that fa(r) ⊆π·fa(l) then one such π can be computed.

Proof

If fa(r) is finite then then problem is easy. If fa(r) is infinite and fa(l) is finite then no such π can exist. Suppose fa(r) and fa(l) are both infinite. By Lemma 5.15 and the construction of permission sets in Definition 2.10, they differ in finitely many atoms. The proof of Corollary 2.52 completes the algorithm.

(A direct proof using Lemma 2.8 is also possible.)End of proof

Lemma 5.17

Suppose r and l are terms and l is closed. Then

1. ∃π, θ.r = π·(lθ) implies

2. ∀π.fa(r) ⊆π·fa(l) ⇒∃θ.r = π·(lθ).

Proof

Suppose fa(r) ⊆π·fa(l) and fa(r) ⊆π′·fa(l) and r = π·(lθ).

We need a θ′ such that r = π′·(lθ′). It follows from the above that (π′-1 ◦π)·fa(lθ) ⊆ fa(l). We use Theorem 5.12.End of proof

Theorem 5.18

If R is closed then R−→ can be calculated as follows, where for simplicity we suppose R = {(l →m)}:

• We try to match r against π·l for some π such that fa(r) ⊆π·fa(l), if such a π exists (if such a π does exist then using Lemma 5.16, it can be computed).

• If we fail then, taking the contrapositive of Lemma 5.17, we must fail for instantiating for any π·l. We descend into subterms of r and repeat the previous step.

To use the matching algorithm of Section 3 to decide rewrites, it suffices that (l, m) satisfy condition 2 of Definition 3.1. So for example, this excludes a rewrite of the form X →δ·X.

6. Conclusions

Many of the proofs above have appeared for the case of nominal terms, e.g. in nominal unification [38], rewriting [12], or permissive-nominal terms [11]. Yet, the approach to unknowns and α-equivalence taken here is different. Definitions and proofs simplify, shorten, and become better-behaved, and new properties emerge. Notably the use of δ simplifies the algorithms.

The infinite permutation δ opens the door to a new set of questions, since our unification algorithm fails if given a problem like X?= δ·X (this would generate an infinite freshness condition that a#X for every a ∈ nontriv(δ) ∩ pmss(X)). But this unification problem goes beyond what can be expressed in nominal unification from [38]. It should be possible to strengthen the algorithm: we would just require infinite (but still computable) freshness conditions. This has already been mentioned in Subsection 9.2 of [12] (closure conditions •t).

We would argue that nominal terms as presented in [38] are not optimal: terms have a freshness context which introduces sequentiality and state into proofs and algorithms; terms cannot be quotiented by α-equivalence; it is unclear how to quantify over unknowns; α-equivalence has an exotic definition and cannot be mapped directly to atoms-abstraction in nominal abstract syntax.

For comparison the syntax in this paper has no freshness contexts; terms can be and are quotiented by binding; universal quantification can be added (see [8, 9, 24]); the definition of α-equivalence is ordinary; characteristic ‘freshness’ conditions on substitutions of nominal unknowns are revealed as corollaries of equivariance (Lemma 2.33); and nominal terms and nominal abstract syntax are made compatible and unified.

There are also mathematical reasons to like the syntax of this paper; it gives us some new theorems. For example, nominal rewriting from [12] and nominal algebra from [27] do not match up. A detailed discussion of this mismatch is in [13], where we go on to make them match up by considering a notion of ‘nominal rewriting in an arbitrarily extended freshness context’. In this paper the mismatch disappears (we have not used the syntax of this paper to build an algebraic logic; for that see [24]). The arbitrarily extended freshness context is already present, in this paper, as the complement of a permission set. The treatment of closed terms is simple and attractive. Syntax can be extended with binders for unknowns, as described in [8, 9, 23]. The nominal HSPA theorem of [21] simplifies to a nominal HSP theorem [24, Section 8].

The price we pay is the complexity in unknowns. In this paper, this involves adding to the syntax injections from natural numbers to atoms. Some readers may object to adding an infinity to syntax. But this is a paper that works from first principles, aimed at a readership of theoreticians who are expected to understand and care about such things. Consider that a presentation of ‘ordinary’ syntax from first principles (using Kuratowski pairs, strings, or initial objects) would look scary—and would include an infinity if there is a quotient by α-equivalence.

In a tutorial exposition we would sweep all this under the carpet and present things more simply, albeit in less detail. We might also wish to generalise the two-level structure of nominal terms, using the model of this paper as a guide: see ‘generalising the treatment of dependencies’ below.

This paper builds on previous ‘nominal’ work as follows: permissive-nominal terms [10, 11] introduced the idea of permission sets for unknowns. An extended abstract proposed to model unknowns as lists [28], taking up ideas about names and well-orderability from an earlier paper [19]; this was followed by a more detailed and extensive journal paper [23]. Of course, this paper also uses [38] and [12] which introduced nominal unification and rewriting. This paper is a sequel to that work.

This paper is also a stepping-stone to further developments. Our suggestion that the approach in this paper has many advantages should not be read as a claim that it has all the answers. Notably in a survey chapter [24]—written after this paper—we generalise the treatment of unknowns to be a strongly-supported nominal set. The difference is that here, the development is concrete and committed to a specific representation of unknowns; whereas the development in [24] is more abstract, pays less attention to computability, and includes material from several other papers.

For future work we have in mind the following:

• It is natural to extend this paper to include nominal algebra [27] and first-order (permissive-nominal) logic [8, 9]. For more on this, see [24].

• We can extend this paper to include λ-abstraction over atoms and over unknowns. This would mirror the development of the Lambda-Context Calculus or Two-level lambda calculus [25, 29].

• We can extend the syntax so that unknowns are not lists of atoms but lists of atoms and finitely many terms; this will allow us to easily define a substitution action for atoms, as is considered (though using a very different presentation) in [16]— if we did this then the theory of unification would become more complex since unification up to a theory of substitution is known to be hard [7]; however, the logical aspects of the syntax should extend smoothly. Here, we would also be moving towards, amongst other things, the enquiry of Kit Fine into ‘arbitrary objects’ [15].

• We can generalise the treatment of dependencies to lose the two-level structure

evident in this paper (atoms depending on nothing, and unknowns depending on infinite lists of atoms) and have instead a general notion of variable and variable-dependency. This would subsume the ideas of nominal techniques into a more general framework.

In developing such future work we expect the concrete model of this paper to be useful as a prototype. It suggests how to generalise nominal permutations and abstractions to variables and variable-dependencies: the generalisation should be consistent with, but not necessarily committed to, mapping a variable to an ordered list of its dependencies. In other words, even if the reader does not care to model meta-variables as lists of ‘lower-level’ variables, we speculate that any sensible model of meta-variables should be consistent with that concrete model.

References

[1] Martín Abadi, Luca Cardelli, Pierre-Louis Curien, and Jean-Jacques Lévy. Explicit substitutions. Journal of Functional Programming, 1(4):375–416, 1991.

[2] Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, Great Britain, 1998.

[3] Christophe Calvès and Maribel Fernández. A polynomial nominal unification algorithm. Theoretical Computer Science, 403:285–306, August 2008.

[4] Christophe Calvès and Maribel Fernández. The first-order nominal link. In Proceedings of Logic-Based Program Synthesis and Transformation (LOPSTR’2010), volume 6564 of Lecture Notes in Computer Science, pages 234–248, 2011.

[5] James Cheney. The complexity of equivariant unification. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), volume 3142 of Lecture Notes in Computer Science, pages 332–344. Springer, 2004.

[6] James Cheney and Christian Urban. Alpha-prolog: A logic programming language with names, binding and alpha-equivalence. In Bart Demoen and Vladimir Lifschitz, editors, Proceedings of the 20th International Conference on Logic Programming (ICLP 2004), number 3132 in Lecture Notes in Computer Science, pages 269–283. Springer, 2004.

[7] Gilles Dowek. The undecidability of unification modulo sigma alone. Manuscript https://who.rocq.inria.fr/Gilles.Dowek/Publi/undecidability.pdf, accessed 18 April 2012.

[8] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic. In Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2010), pages 165–176. ACM Press, 2010.

[9] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic (journal version). Transactions on Computational Logic, 2012. In press.

[10] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification. In Proceedings of the 24th Italian Conference on Computational Logic (CILC’09), 2009.

[11] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification: an infinite, co-infinite approach to nominal techniques (journal version). Logic Journal of the IGPL, 18(6):769–822, 2010.

[12] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, June 2007.

[13] Maribel Fernández and Murdoch J. Gabbay. Closed nominal rewriting and efficiently computable nominal algebra equality. In Electronic Proceedings in Theoretical Computer Science, volume 34, pages 37–51, 2010.

[14] Maribel Fernández, Murdoch J. Gabbay, and Ian Mackie. Nominal Rewriting Systems. In Proceedings of the 6th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming (PPDP 2004), pages 108–119. ACM Press, August 2004.

[15] Kit Fine. Reasoning with Arbitrary Objects. Blackwell, 1985.

[16] Marcelo Fiore and Chung-Kil Hur. Second-order equational logic. In Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL 2010), Lecture Notes in Computer Science. Springer, 2010.

[17] Marcelo P. Fiore, Gordon D. Plotkin, and Daniele Turi. Abstract syntax and variable binding. In Proceedings of the 14th IEEE Symposium on Logic in Computer Science (LICS 1999), pages 193–202. IEEE Computer Society Press, 1999.

[18] Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, University of Cambridge, UK, March 2001.

[19] Murdoch J. Gabbay. FM-HOL, a higher-order theory of names. In F. Kamareddine, editor, 35 Years of Automath, April 2002.

[20] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205(7):982–1011, July 2007.

[21] Murdoch J. Gabbay. Nominal Algebra and the HSP Theorem. Journal of Logic and Computation, 19(2):341–367, April 2009.

[22] Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 17(2):161–229, 2011.

[23] Murdoch J. Gabbay. Two-level nominal sets and semantic nominal terms: an extension of nominal set theory for handling meta-variables. Mathematical Structures in Computer Science, 21:997–1033, 2011.

[24] Murdoch J. Gabbay. Nominal terms and nominal logics: from foundations to meta-mathematics. In Handbook of Philosophical Logic, volume 17. Kluwer, 2012.

[25] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus (extended version). Information and computation, 207:1369–1400, December 2009.

[26] Murdoch J. Gabbay and Aad Mathijssen. A Formal Calculus for Informal Equality with Binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of Lecture Notes in Computer Science, pages 162–176. Springer, July 2007.

[27] Murdoch J. Gabbay and Aad Mathijssen. Nominal universal algebra: equational logic with names and binding. Journal of Logic and Computation, 19(6):1455–1508, December 2009.

[28] Murdoch J. Gabbay and Dominic P. Mulligan. Semantic nominal terms. In Proceedings of the 2nd International Workshop on the Theory and Applications of Abstraction, Substitution and Naming (TAASN 2009), March 2009.

[29] Murdoch J. Gabbay and Dominic P. Mulligan. Two-level lambda-calculus. In Proceedings of the 17th International Workshop on Functional and (Constraint) Logic Programming (WFLP 2008), volume 246, pages 107–129, August 2009.

[30] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, 13(3–5):341–363, July 2001.

[31] Gerhard Gentzen. Untersuchungen über das logische Schließen [Investigations into logical deduction]. Mathematische Zeitschrift 39, pages 176–210,405–431, 1935. Translated in [37], pages 68–131.

[32] Jordi Levy and Mateu Villaret. An efficient nominal unification algorithm. In Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA 2010), volume 6 of Leibniz International Proceedings in Informatics (LIPIcs), pages 209–226. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2010.

[33] Jordi Levy and Mateu Villaret. Nominal unification from a higher-order perspective. Transactions on Computational Logic, 2012. to appear.

[34] Dag Prawitz. Natural deduction: a prooof-theoretical study. Almquist and Wiksell, 1965.

Reprinted by Dover, 2006.

[35] Barry K. Rosen. Tree-manipulating systems and church-rosser theorems. Journal of the ACM (JACM), 20(1):160–187, 1973.

[36] Raymond Smullyan. First-order logic. Springer, 1968. Reprinted by Dover, 1995.

[37] M. E. Szabo, editor. Collected Papers of Gerhard Gentzen. North Holland, 1969. [38] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, September 2004.

Acknowledgements

We are grateful to Jane Spurr and to two anonymous referees for their expertise and support. We also acknowledge the support of the Leverhulme trust, of grant DE-SAFIOS10 (TIN2009-14599-C03-03) from the Spanish Ministry of Science and Innova-tion, and of grant PROMETIDOS (P2009/TIC-1465) from the Madrid Regional Govern-ment.

Notes

1Note that ‘generated as a group’ means that every element can be expressed as a finite compositions of the generating elements. Thus for example, δ is not generated by swappings. ↩

2Having π and π′ on the left is not a typo. ↩

3Using Lemma 2.16 this equivalence class may also be written {x′ | orb(x′) = orb(X)}, where here x′ ranges over all unknowns. (We write x′ rather than X′ here because by our permutative convention in Definition 2.15, X′ ranges only over unknowns such that orb(X) and orb(X′) are distinct.) ↩

4Taking the inverse here saves writing -1 quite so many times in Definition 2.48, and is harmless since permutations are invertible. ↩

5The interested reader might compare this with the corresponding case in the proof of [11, Lemma 3.8], also using a permissive-nominal syntax but without taking meta-variables as infinite lists. ↩

6In Remark 2.11 our slogan was that a nominal unknown is an infinite list of distinct atoms. An extension of this slogan is to allow unknowns to be an infinite list of distinct atoms, except for finitely many entries which are allowed to be terms. We do not do that in this paper because we are interested in modelling α-equivalence without atoms-substitution as primitive. If we did allow this, then our model of syntax would be appropriate to permit an atoms-substitution action [a:=t] as primitive (the disadvantage of this is that it would greatly complicate the theories of rewriting, unification, and algebra—but sometimes we just want substitution around). In any case, if we did this then the atoms-substitution would be able to act on Z where a ∈ pmss(Z), by actually replacing a in Z by t. We return to this briefly in the Conclusions. ↩

7The interested reader can begin by comparing our notion of closed terms in Definition 5.7, based on two simpler inductive definitions, with that used in [12, Definition 68], based on a renamed variant of a term and an equality derivable in an extended freshness context. ↩