Meta-variables as infinite lists in nominal terms unification and rewriting
Source watermark: DRAFT
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 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.
Fix two disjoint countably infinite sets and of atoms and write
will range over distinct elements of ; we call this the permutative convention.
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.
Fix a bijection from non-positive integers -3 -2 -1 0 to . Fix a bijection from positive integers 1 2 to . Write their combination ; this is a bijection from integers to atoms.
Given write () for the swapping bijection on atoms specified by:
Recall that by our permutative convention , , and are distinct. By convention () will denote the identity function on atoms id.
Write for the shift permutation which maps () to (1) for 0, and (2) to (2(1)) and (2 to (2 for 1. So:
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 such that (, so we can always choose an atom ‘fresh’ for (we use this for instance in part 2 of Definition 2.44).
bijects with (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.
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 ()((())). Write id for the identity permutation (so id( always).
() (() ()).
As a corollary, any may be uniquely written as , and concretely represented as the pair (), for some and some finite .
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 () and shift permutation .
Give sets of atoms the pointwise permutation action given by () .
A permission set is a set of the form .
will range over permission sets.
2.2. Unknowns
The slogan of this subsection is:
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.
For each prime number 2 define a bijection on non-positive integers which for every 0 maps - to - and maps - to -, and is the identity elsewhere:
Let range over the group generated by the .
Every may be represented canonically as a finite list of unique generating elements in numerical order.
The generators biject with the prime numbers and form an involutive and com-mutative group.
A level 2 variable or unknown is a bijection from non-positive integers to a permission set , of the form .
We may consider as a tuple and write for () and write ) or even ).
Write orb() for the unique such that for some .
, , will range over unknowns. By convention, and will range over unknowns such that orb() and orb() are distinct; this is a form of permutative convention.
Write pmss() for the permission set of defined by 0.
A fact of the way we constructed the groups that and inhabit.
may be finitely represented as a pair () where is a permutation and is a finite set of prime numbers. As a corollary, equality of unknowns is decidable and orb() is quickly calculated from a reasonable finite representation using second projection.
For every permission set there are infinitely many unknowns with distinct permutation orbits such that pmss(.
2.3. Terms
We quotient terms by -equivalence, where [] binds in and we treat as a(n infinite) tuple. We may assume tupling term-formers and write () or ().
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.
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 ‘13’ (whose decimal representation is infinite but which has a compact representation as . . . 13), ‘the number ’, ‘the -equivalence class of the -term ’, and ‘the set of natural numbers’.
Note the ‘pointwise’ nature of the clauses for fa() and . An unknown can be split up into ‘a and a ’ (see Lemma 2.16). This mirrors the moderated unknowns used in [38, 11].
If then ) .
[]] if and only if fa() and ().
[]] if and only if for fresh (so fa()fa()) ()).
fa(fa().
Routine induction on .
If (() for all fa() then .
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 . We consider two cases:
The case of . It is a structural fact of the pointwise permutation acting (Definition 2.23) that if (() for all fa() then (() for all appearing in considered as a tuple, and so .
The case of []. From part 2 of Lemma 2.25, given that we -converted all bound atoms to be fresh for the permutations.
2.4. Free unknowns of a term
Defining a notion of ‘the free unknowns of ’ is not entirely evident.
Consider for example [] where pmss(). If ‘ appears in []’ is true then so is ‘() appears in []’ for any pmss(), since []](). 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.
By abuse of notation we write fv() for orb() fv() and fv() for orb() fv(), and so forth.
fv() is well-defined.
2.5. Substitutions
We call equivariant. will range over substitutions.
Write id for the identity substitution mapping to 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(()) pmss()’ as in Definition 3.1 of [11]. In the context of this paper, that condition follows as a corollary of equivariance:
If is a substitution then fa(()) pmss() for all unknowns.
Suppose there exists fa(()) pmss(). Choose fresh (so fa(()) pmss()). Lemma 2.26 implies that ()() (). Yet since pmss() also (). Thus () )((()(), a contradiction.
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.
Unknowns from (permissive) nominal terms correspond to representatives of permutation equivalence classes.
In this paper both and are -tuples of atoms with equal standing in an equivalence class of unknowns of the form a permutation.3
When we specify [] we have chosen a particular representative . To specify the action of [] on all unknowns we must consider unknowns in the permutation equivalence class of , 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’ in Definition 2.34 is an artefact of our writing [] instead of a mathematically equal [] for some other .
Since is constrained to be equivariant its behaviour on is already determined by its behaviour on and so we could unambiguously specify [] succinctly just as []( and []( , or even (being just a little lax) just as [](.
Note that refers to acting on as a term whereas () refers the value of the function at .
().
By a routine induction on using equivariance.
fa() fa().
By induction on using Lemma 2.33.
is well-defined.
If (() for all fv() then .
2.6. shift-permutation
The reader may be familiar with the de Bruijn shift function [1, Subsection 2.2]. This maps to 0 by mapping to , 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 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 and atom there exists some such that . 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.
The algorithm from [11, Section 6] used a notion of the ‘known unknowns’ 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 #.
Very broadly speaking, the reader can translate ‘#’ in [38] to ; the use of in the unification algorithm of Section 3, parallels the use of # in [38].
Recall the bijection from integers to atoms from Definition 2.3. By abuse of notation write 0 for the atom (0).
1. If then define by:
2. If then for some fixed but arbitrary choice of such that ( (and so also ), define by:
1. If then bijects with .
2. If then bijects with .
For the first part, suppose . Then 0). We reason as follows:
Now suppose . It is easier to work with ()-1, to keep the parallel with the previous case. So 0)) 0. We reason as follows:
Recall from Definition 2.10 that each permission set has the form for some permutation .
For each make some choice of permutation such that .4
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.
1. bijects with .
2. bijects with .
From Lemma 2.46.
Suppose is a permission set and pmss(. Suppose is a finite list of atoms and is a finite list of atoms . Suppose and . Then define and , and - and by:
Suppose is a permission set. Suppose and are finite lists of atoms and . Suppose and .
Then bijects with and bijects with .
Using Lemma 2.49.
is a permission set if and only if ) for some finite and .
2.7. Invertible substitutions
In this brief subsection we discuss some simple constructions which will be useful later.
() ().
Call invertible when there exists such that id.
is invertible if and only if is a bijection on the set of all unknowns. Furthermore, if is invertible then pmss(( pmss() always.
Substitution cannot make syntax smaller, or (by Lemma 2.38) make free atoms larger.
Given any finite set of unknowns there exists an invertible substitution such that for every it is the case that orb(()) orb() .
Using Proposition 2.18.
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 ). However, the invertible construction is no harder and is also a special case of a more abstract framework explored elsewhere [23].
2.8. Occurrences
As discussed in Remark 2.28 we have to be careful if we wish to say ‘ appears in ’; this might not quite mean what we think it does.
For example if ‘ appears in []’ where pmss() then also ‘() appears in []’ for any pmss(), since []]().
We dealt with this in Definition 2.29 by quotienting out all permutations. But this is a little drastic.
For instance, ‘() appears in []’ is not true for pmss(); it is not the case that if ‘ appears in ’ then ‘ appears in ’ for any .
We did not need to quotient out all permutations—only some of them—and so re-turning orb() 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 ‘ appears in under a list of abstractions ’. This will be useful later.
will range over finite lists of distinct atoms. A (level 2) occurrence is a term of the form [] where [] is and [] is [][].
occurs in .
[] occurs in [] and also in [](); so does [] . does not occur in [] or []().
Suppose is fresh (so ). Then [][] and [][]() occur in []([] []). We quotient terms by -equivalence, so [][]() is equal to [][] and thus [][] occurs in []([] []).
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 #. 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 ; see for instance Figure 5 of [11]. The job of 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
An equality is a unordered pair (so is identical to ) such that:
1. sort( sort().
2. If [] and [] are both in occ() occ() then is finite. So we exclude an equality like , where is a shift permutation and nontriv() pmss() is not finite.
A freshness is an ordered pair #.
Let ef range over equalities or freshnesses and define ef by:
A unification problem is a finite list .
We (ab)use standard sets notation and write ef as shorthand for ‘ef appears in the list ’.
Condition 2 in Definition 3.1 protects (X) in Figure 1 from an ‘infinite freshness explosion’, if nontriv()pmss() 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.
Sol() if and only if Sol().
Define a simplification rewrite relation 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 .
The instantiating rule (IF) preserves condition 2 of Definition 3.1 because it applies [] uniformly to all occurrences involving . Condition 2 does not outlaw , it just outlaws attaching it to one occurrence of and not another.
Unlike was the case in [38], there is no separate simplification rule for [] []. This is because we have quotiented syntax by -equivalence, so and can both be renamed to some fresh . 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.
If is a problem, define a unification algorithm by:
1. Rewrite 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.
In Definition 3.8, we apply each rule to the head of the list . This is to prevent ‘unfair’ looping, e.g. repeatedly applying (F) to some equality wherever it appears in .
We note in passing that the rule (F#) is equivalent—in the presence of the other rules—to a pair of rules # and # if pmss().
The algorithm of Definition 3.8 always terminates.
It is not hard to generate an inductive quantity which is reduced by the reductions in Figure 1.
In [33] it is suggested to implement freshness conditions in nominal unification using equality conditions of the form []]. 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 []] is identical to []()]() for fresh , because we already quotiented by -equivalence. This equality in turn has the same value as ())—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 -quantifier from [30]: we could encode # as ) for pmss().
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 - from Definition 2.48.
Example one (succeeds).
Suppose and . Take pmss( and suppose a term-former g. We apply the algorithm to g([] []) g([] []):
Example two (succeeds).
Suppose and . Take pmss(, pmss(, and pmss(. Suppose a term-former f.
We apply the algorithm to f([]) f([] []):
Example three (fails).
Take pmss(. We run the algorithm on [][]]:
The algorithm fails because the precondition of rule (IE), fv([]) is not satis-fied.
Example four (succeeds).
Take pmss( and take . We run the algorithm on ):
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
If by a non-instantiating rule (Definition 3.5) then Sol( Sol().
The empty set cannot be simplified, so suppose where the simplification rule acts on . We consider two cases:
The case (. Suppose ]] and []] by (. By Definition 2.36 and properties of equality, [](]() if and only if .
The case (Ff). Suppose #?f() and #?f() ## by (Ff). By Definitions 2.36 and 2.23, fa(f()) if and only if fa(), ..., fa().
The case (F). Suppose and pmss()fa(), and # by (F). Now if solves then (. By Lemma 2.38 fa() pmss() and so in particular also solves #. The result follows.
if and only if fv()(().
By a routine induction on . We consider two cases:
The case []. Suppose (() for every fv([]). fv([] fv() so by inductive hypothesis . The result follows from the definitions. The reverse implication is similar.
The case . Suppose (() for all . Then taking id we have ((. Conversely if then by equivariance (Definition 2.32) (() for all .
Suppose (() for all fv(). Then Sol() if and only if Sol().
3.3.2. ...under (IE)
Recall from Remark 2.35 the discussion of why we write when we have chosen a representative element of an equivalence class of unknowns under permutations.
In the right circumstances, a substitution can be factored as ‘a part of that does not touch ’ and ‘a single substitution for ’:
If and fv() then ](). That is,
We reason as follows:
3.3.3. ...under (IF)
It is routine to verify that Definition 3.18 is well-defined and a substitution.
Suppose pmss() and fa(()). Then
We unpack definitions:
3.4. Simplification rewrites calculate principal solutions
Write when there exists some such that () always. Call the instantiation ordering.
If then .
By Definition 3.20, exists such that () always. Then:
1. Suppose fa()pmss() and fv(). Write ]. If
2. Suppose pmss(). Write -]. If with (IF) then Sol() implies Sol().
If then is a principal solution to (Definition 3.21).
By induction on the path of .
The empty path. So and id. By Definition 3.20, id .
The non-instantiating case. Suppose
where by a non-instantiating rule. By inductive hypothesis is a principal solution of . It follows from Lemma 3.12 that is also a principal solution of .
The case (IE). Suppose fa() pmss() and fv(). Write ]. Suppose so that
Further, consider any other Sol(). By Lemma 3.23 () Sol() and by inductive hypothesis Sol() and . By Lemma 3.22, (). By Theorem 3.17 ( .
The case (IF). Suppose pmss(). Write -], so that
Further, consider any other Sol(). By Lemma 3.23, Sol() and by inductive hypothesis Sol() and . By Lemma 3.22, . By Theorem 3.19 .
Given a problem , if the algorithm of Definition 3.8 succeeds then it returns a principal solution; if it fails then there is no solution.
If the algorithm succeeds we use Theorem 3.24. Otherwise, the algorithm gener-ates an element of the form f() f() where , f() g(), f() ], f() , [], [], , #, or where fv(). 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 exists.
Fix terms and .
Call nominal unification the problem of finding a to make .
Call nominal matching the problem of finding a to make .
Nominal unification and nominal matching are decidable.
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 so they are disjoint from unknowns in and run the unification algorithm with the mod-ification that it should not trigger (IE) or (IF) for fv(). It is not hard to see that this calculates a most general matching solution.
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
A rewrite rule is a pair such that fv() fv(). 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.
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([]) to and app() to and var() to .
An axiom for -reduction is:
Here is that same -equivalence axiom, written out as it would be informally:
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 () to [] then rewrites for -reduction are:
There is no rule for the general case of [] where pmss()—this does not reduce. Similarly in informal practice we cannot say anything about the reductions of the schema of terms represented by () without knowing any further particulars of what and 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.
Define the terms in which occurs only once by:
A position is a pair () of a nominal term and an unknown which occurs only once in .
In Definition 4.3, denotes an unknown in the same permutation equivalence class as . For example:
occurs only once in .
occurs only once in (recall that is a well-ordering of pmss()).
and do not occur in a such that orb() orb().
If ) is a position write pmss() for pmss().
If fa() pmss() (so that [] is a substitution) write [] for [].
The multi-step rewrite relation is the reflexive transitive closure of the one-step rewrite relation.
Note that implies holds by construction because of the in Definition 4.3.
Recall the rule () from Example 4.2: () where pmss().
To deduce () where pmss() we take )) for some pmss() and we take ].
To deduce () we also take )) and ]. This is because () and () are -equivalent and we (use nominal abstract syntax or) quotient syntax by -equivalence.
To deduce () we take ) and id.
Suppose pmss( pmss() . To deduce () we take (()-) and ].
We cannot deduce () , because [] is not a substitution: no function mapping to can be equivariant, since () but () (also pmss(): see Lemma 2.33).
Some terminology will be useful later, so we introduce it now in one place:
4.2. Peaks, critical pairs, joinability
We now investigate criteria for deducing confluence of nominal rewrite systems.
Consider two rewrite rules ) and ). Call a copy of when there exists an invertible substitution (Definition 2.55) such that (.
Clearly, if is a copy of then is also a copy of . Furthermore:
If and are copies of the same rule then if and only if .
Unpacking Definition 4.6 and exploiting the existence of an inverse .
Write when and and call this a peak. Call this peak joinable when there exists a such that and .
So R is locally confluent when every peak is joinable.
Suppose that ) for 2 and fv() fv(. Suppose [] for some and has a principal solution . Call the pair ([]) a critical pair.
Call ([]) trivial when at least one of the following hold:
1. ) and and are copies of the same rule.
2. for some unknown .
Peaks that are instances of trivial critical pairs, are not always joinable.
It suffices to provide a counterexample. Fix term-formers 0 and f and take (0 ) and f()) where pmss().
There is a critical pair ( f()) between and .
Also, 0 and 0 f() and it is a fact that this peak cannot be joined—we ‘want’ to close this peak by rewriting to f() using , but the fact that pmss() blocks this.
In nominal rewriting from [12] it was not in general the case that if and then (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
If fa() fa() then fa([]) fa([]).
) is uniform if and only if fa() fa().
Suppose ) is uniform and fv(). Suppose (. Specify by (() and ((). Then for any .
If a rewrite theory R (Definition 4.1) is uniform then peaks that are instances of trivial critical pairs, are joinable.
Consider two rules ) R for 2. Without loss of generality we suppose the unknowns of are disjoint from those of . Suppose they have a critical pair ([]). That is, there exists such that [] and is a principal solution to .
There are two cases:
The case ) and and are copies of the same rule . The peak we want to join is , where the rules and 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() fv().
The case []) where [] and (. Specify by ( and (() for all other ; note that is a substitution since fa() fa() by uniformity and fa() pmss() by our assumption that is a substitution. By Lemma 4.19 . By definition [], so we have joined the peak.
Suppose R is uniform and all non-trivial critical pairs of R are joinable. Then R is locally confluent.
Suppose and . Write and for the positions at which the two rewrites occur.
If and identify distinct subterms of then local confluence holds by a standard diagrammatic argument (see for instance [2]).
Otherwise it must be that []); that is, identifies a point in beneath the point identified by (or the symmetric case that []), which is similar and we elide). There are now three possibilities:
1. in replaces an unknown in . This is an instance of a trivial critical pair; we use Theorem 4.20.
2. ) and and 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.
4.4. Terminating rewrite systems
Call a rewrite system R terminating when all rewrite sequences are finite. Call a term a normal form (with respect to a rewrite system R) when ( ), that is, when does not R-rewrite to anything.
Suppose R is terminating, uniform, and suppose non-trivial critical pairs in R are joinable. Then:
1. R is confluent.
2. If and and and are normal forms, then .
4.5. Orthogonal rewrite systems
Call ) left-linear when each unknown occurring in occurs only once (Definition 4.3).
For example f() g() is left-linear but g() f() and g() f() are not. Note that () is left-linear.
Call R orthogonal when every R is uniform and left-linear, and all critical pairs are trivial.
Suppose ). Write when and the rewrite occurs at a position ). We say that the rewrite with occurs at root position.
Expanding Definition 4.26, when there exists and such that () and (). For example: if ) then but not [] [].
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.
We define a parallel reduction relation by the rules in Figure 2.
If R is orthogonal then is strongly confluent (Definition 4.9), and therefore confluent.
We prove by induction on the derivation of that for all if then there exists some such that and . We consider a selection of cases:
The derivations of and both end in (f). We use the inductive hy-potheses and (f).
The derivation of ends in (f) and that of ends in (). So and for 1 , and f(() () for some and ) R. By inductive hypothesis there exist such that and We now proceed as illustrated and explained below:
Either is an unknown or the rewrite f() f() takes place in the substitution . If is an unknown then by uniformity we may rewrite () using and close the diagram by rewriting corresponding instances of () in (). Otherwise, by uniformity there is a substitution such that () () for every and f((). Rules are also left-linear so still applies to (): f() () and therefore f() by () for . The other cases are no harder.
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.
5. Closed terms
Equivariant unification—the problem of finding and such that (—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 rewrites with a rule (), 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
The explicit atoms of are the atoms that actually appear (unbound) in . Contrast this with fa() which is intuitively the atoms that might appear in (perhaps after a substitution). For instance, ea( pmss( fa().
Recall the notion of the occurrences in from Subsection 2.8.
Write occ([] [] occ(). Also if ] and is a permission set define .
ea(ea() and occ(occ(). In addition, ea() ea().
By routine inductions on .
fa( ea() fa([]) [] occ().
Unpacking Definition 2.23, fa( ea() pmss() [] occ().
Call occ() fa-functional when if [] occ() and [] occ() then fa([] fa([]) (equivalently, when and contain the same atoms but not necessarily in the same order).
is not closed (ea is non-empty).
is closed.
([]) is not closed (occ is not fa-functional).
[]() is closed.
Suppose ea(. Then ( if and only if (([])]) for every [] occ().
By a routine induction on (actually a nominal induction, since we -convert). We consider some cases:
The case . By definition occ(. The result is immediate.
The case . ea() so there is nothing to prove.
The case []. -renaming if necessary, suppose (. By definition occ([] [] [] occ(). Suppose (([])]), so that from Definitions 2.23 and 2.36 and by Lemma 2.25, (. By inductive hypothesis (([])]). It follows that (([])]). The reverse implication is similar.
We need Definition 5.10 and Proposition 5.11 for Theorem 5.12.
Suppose we are given the following data:
For each (Definition 2.15) a fixed but arbitrary choice of representative such that orb(.
For each a choice of term such that fa() supp().
Define the equivariant extension of this data by:
1. The equivariant extension from Definition 5.10 is well-defined and is a substitution.
2. Every substitution is an equivariant extension.
is closed if and only if
Suppose there is a permission set fa() such that if fa() then there exists such that (. There are two things to prove:
ea() is empty. Suppose there exists ea(). Pick ea(). By assumption taking id there exists such that ()(. By Lemma 5.4 ea(() ()ea() and ea() ea(), a contradiction.
occ() is fa-functional. Consider [] and [] in occ(); choose such that fa( for 2. Suppose there exists fa([]) fa([]), and choose any fa([]) (since pmss() is infinite and is finite, such a exists). By Lemma 5.5 fa() so by assumption taking id there exists such that (). By Lemma 5.9 ()[]]). By Lemma 2.26 is free in the left-hand side, and by Lemma 2.38 is not free in the right-hand side; a contradiction.
Suppose occ() is fa-functional and ea( and choose some permutation and substitution .
If occ( then by Lemma 5.5 fa( so by Lemmas 2.27 and 2.40 ( and , so there is nothing to prove.
Otherwise take fa(). For every element of occ() make a fixed but arbitrary choice of representation as [] where the atoms in are disjoint from the atoms in nontriv(). We take to equivariantly extend this choice (Definition 5.10), so we map to ()() for the choice of representing above, and otherwise to map to . Using Proposition 5.11 this is a substitution and (([])]) for every [] occ(). We use Lemma 5.9.
5.2. Closed rewrite rules
Recall that uniform rules satisfy Theorems 4.29 and 4.21.
If ) is closed then it is uniform.
By assumption fv() fv(). Also () is fa-functional; it follows that occ() occ(). The result follows from Lemma 5.5.
If fa() is infinite then fa() is a permission set.
For any terms and , if there exists a such that fa() fa() then one such can be computed.
If fa() is finite then then problem is easy. If fa() is infinite and fa() is finite then no such can exist. Suppose fa() and fa() 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.)
Suppose and are terms and is closed. Then
1. () implies
2. fa() fa() ().
Suppose fa() fa() and fa() fa() and ().
We need a such that (). It follows from the above that ()fa() fa(). We use Theorem 5.12.
If R is closed then can be calculated as follows, where for simplicity we suppose R ():
We try to match against for some such that fa() fa(), 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 . We descend into subterms of and repeat the previous step.
To use the matching algorithm of Section 3 to decide rewrites, it suffices that () satisfy condition 2 of Definition 3.1. So for example, this excludes a rewrite of the form .
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 (this would generate an infinite freshness condition that # for every nontriv() pmss()). 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 ).
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 orb( orb(), where here ranges over all unknowns. (We write rather than here because by our permutative convention in Definition 2.15, ranges only over unknowns such that orb() and orb() 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 [] 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 where pmss(), by actually replacing in by . 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. ↩