NOMINAL ALGEBRA
Abstract. Nominal terms are a term-language used to accurately and expressively represent systems with binding. We present Nominal Algebra (NA), a theory of algebraic equality on nominal terms. Built-in support for binding in the presence of meta-variables allows NA to closely mirror informal mathematical usage and notation, where expressions such as or are common, in which meta-variables and explicitly occur in the scope of a variable . We describe the syntax and semantics of NA, and provide a sound and complete proof system for it. We also give some examples of axioms; other work has considered sets of axioms of particular interest in some detail.
1. Introduction
Universal algebra [6, 18, 5] is the theory of equalities . It is a simple framework within which we can study mathematical structures, for example groups, rings, and fields. It has also been applied to study the mathematical properties of mathematical truth and computability. For example boolean algebras correspond to classical truth, heyting algebras correspond to intuitionistic truth, cylindric algebras correspond to truth in the presence of predicates as well as propositions, combinators correspond to computability, and so on.
Informal mathematical usage and notation often involve binding. In many cases, this involves freshness and -equivalence in the presence of meta-variables. For example:
-calculus: ( — if does not occur free in (is fresh for) .
-calculus: () () — if is fresh for .
First-order logic: () () — if is fresh for .
Here , , , and are meta-variables ranging over concrete terms.
Now take any binder . Then:
()[([]) — if is fresh for .
-equivalence: [] — if is fresh for .
Nominal terms [26, 27] are a syntax designed to naturally express binding, freshness and -equivalence in the presence of these meta-variables. This paper studies the theory of equality between nominal terms. We obtain Nominal Algebra (NA). This permits direct and intuitive axiomatisation of systems with binding and yet we keep the flavour of ‘normal algebra’.
In other published work we have already applied nominal algebra to investigate specific axiomatic systems for truth and computability [12, 13]. In this paper we present a common syntax and semantics for Nominal Algebra, together with a sound and complete proof system.
2. Syntax
2.1. Sorts, terms and signatures.
In this paper we consider a sorted NA; an unsorted version would also be feasible. Fix disjoint collections of base sorts and atomic sorts . For our examples we need only one atomic sort, so we may write for the atomic sort.
Then sorts and arities are defined by the following grammars:
Here may be zero, in which case we write () as .
For each atomic sort fix a countably infinite collection of atoms , representing object-variables. For each sort fix a countably infinite collection of unknowns , representing meta-variables. All these collections are assumed disjoint. We may omit the subscripts. We call where stands for a permutation of atoms a moderated unknown. This represents a permutation of object-variables that is performed when the meta-variable is instantiated to a concrete term. We will explain later how these permutations on unknowns facilitate -conversion on nominal terms.
Fix term-formers f to each of which is associated some unique arity . We may write f : for ‘f, which has arity ’.
Terms are inductively defined by:
We define sorting assertions inductively by:
Here [] is called an abstractor; it represents a term in which an object-variable is abstracted.
A signature Σ is a triple containing finite sets of base sorts, atomic sorts, and term-formers with associated arities.
A signature for. . .
the -calculus consists of base sort , atomic sort , and term-formers var : (), app : (), and : ([]). Note how this mirrors the specification of -calculus syntax. var is needed to turn an atom into a term of sort ; this is a standard device called a casting function. We generally sugar app() to and ([]) to [].
first-order logic with equality has base sorts and , atomic sort , and term-formers : , : (), : ([]), : (), and var : (). We sugar () to , ([]) to [] and () to .
A permutation of atoms is a bijection with finite support. That means that for some finite set of atoms (which may be empty) () , and for all other atoms (. For further discussion of permutations of atoms see elsewhere ([15], [27], and [10, Section 5.4]). Write Id for the identity permutation, for the inverse of , and for the composition of and , i.e. ()((()). Id is also the identity of composition, i.e. Id and Id . Write () for the permutation that swaps and , i.e. the permutation that maps to , to and all other to themselves. We abbreviate Id to .
In the presence of multiple atomic sorts we assume that () must have the same sort as ; so permutations are sort-respecting.
Write for syntactic identity of terms. There is no quotient by abstraction so for example [] []. Say that a term is closed when it does not contain any unknowns. Write for ‘ occurs in (the syntax of) ’, and for ‘ occurs in (the syntax of) ’. Occurrence is literal, e.g. [] and when () . Similarly write and for ‘does not occur in the syntax of ’.
2.2. Judgements, axioms and theories.
A freshness (assertion) is a pair # of an atom and a term . An equality (assertion) is a pair where and are terms of the same sort. Call a freshness # (so ) primitive. Write ∆ for a finite set of primitive freshnesses and call it a freshness context. We drop set brackets in freshness contexts, e.g. writing ## for ##.
A judgement is a pair ∆ of a freshness context and an assertion. We may call it an equality (or freshness) judgement, if is an equality (or freshness) assertion. We may write as .
We allow equality judgements ∆ as axioms (made formal later). We do not allow freshness judgements as axioms; we shall see that they can be easily expressed using equalities instead.
A theory T Ax) is a pair of a signature Σ and a possibly infinite set of axioms Ax on that signature. We name theories in sans serif font.
CORE is a theory with an atomic sort and one axiom
This theory expresses -equivalence in the presence of meta-variables (made formal by Theorem 4.5). Henceforth we shall consider only theories containing (perm).
SUB has a signature with a base sort , a sort of atoms , a substitution term-former sub : ([]) for each [], additional term-formers (say) app : () and lam : ([]), and a variable casting term-former var : (). We sugar sub([]) to []. SUB has the following axioms:
A detailed study of SUB can be found in [12].
LAM takes SUB and adds the axiom ([])[]. Here we use sugar from Example 2.1.
In other work we investigate a theory FOL for the signature of first-order logic mentioned above [13].
We are not concerned in whether the above theories have some other base data sorts, so the reader should consider these examples to be parametric over such choices. As mentioned above, we only consider theories extending CORE.
3. Semantics
Nominal sets are the natural model of nominal terms (the sets came first [15]). Write for the set of all permutations. A permutation action on a set is a function : , write it infix as , such that Id and () . It is easy to prove that is always bijective as a function on . Call a pair () of a set and a permutation action on it a set with a permutation action. We generally write both for the set and for ().
has the natural permutation action given by ().
The powerset of , write it has the natural permutation action given by the pointwise action .
Call cofinite when is finite. The set of finite and cofinite subsets of , write it finite or cofinite inherits the pointwise action from . (fs stands for finite support; more on this soon.)
We assume these permutation actions on these sets henceforth. Given a formula on atoms, write () (the Gabbay-Pitts NEW quantifier [8, 15]) for the assertion ‘() is false for finitely many atoms (perhaps none), and true for all other atoms’. This is a mathematical notion of ‘() for most ’. For and write # when () . Read this as is fresh for .
For , # when .
For both and , # when is finite and , or when is cofinite and . For example, # but not #.
We can think of # as an abstract notion of ‘does not occur in any distinguished manner’. We say ‘distinguished’, because the last example of shows that # is not the same as : for example () but not #().
Call a nominal set when #, i.e. () . This property expresses finite support [15, 23]. Henceforth and range over nominal sets. Of the examples above, all except for are nominal sets [8].
Write for the set () with the pointwise permutation action (). The abstraction set [] is quotiented by a relation given by () () when () ) . Write [] for the -equivalence class of (). The elements of [] validate the characteristic property of -equivalence that if # then []]() (detailed accounts of this are elsewhere [15, 8]). Both and [] are a nominal sets.
Functions : (on the underlying sets) have a natural conjugation permutation action given by ()( (()). Call equivariant if for all , i.e. if ((() always.
We can now give a semantics to NA theories. An interpretation of a signature assigns a nominal set to each base sort and an equivariant function f () to each term-former f : ().
is inductively defined by:
An evaluation maps unknowns to elements () . An interpretation and evaluation extend to terms
We can now define validity of assertions, freshness contexts and judgements:
# (is valid) when # when
when #() for each #
when for all evaluations
Then a model of a theory T is an interpretation of its signature such that for all axioms ∆ of T. So a model of an NA theory is just like a model of any other algebraic theory, but we must interpret atoms by atoms, permutations by permutations, abstractions by abstractions, and term-formers by equivariant functions on underlying sets.
Write ∆ if for all models of T. Say that ∆ validates in theory T.
4. Derivability
4.1. Permutation and substitution actions.
Substitution is the mechanism by which unknowns become terms, and is necessary in algebra in order to define instances of axioms. Formally a substitution is a finitely supported function from unknowns to terms of the same sort. Here, finite support means: for some finite set of unknowns () , and for all other unknowns () . Write [] for the substitution such that () and () , for all , 1 .
In order to define the inference rules of NA, we need to be able to apply permutations and substitutions to terms. Write for the action of a permutation on a term , defined by:
Composition and identity of permutations also extend to terms.
() () and Id .
By straightforward induction on the structure of , using the definition of
Write the action of a substitution on a term as and define it by:
Note that substitution does not avoid capture, i.e. ([])[] []. It reduces parentheses to give substitution a higher priority than permutation and abstraction, so we do. Write for composition, i.e. () ().
The following commutation is easy to prove [27, 7]:
().
By straightforward induction on the structure of , using the definitions of and .
Another permutation action is useful. Write for the meta-level action of on , inductively defined by:
Also for this permutation action, composition and identity of permutations extend to terms.
and .
By straightforward induction on the structure of , using the definition of .
Permutation actions and are interdefinable; sometimes one is more convenient than the other.
Given a term let and be substitutions that map each to and , respectively. Then and ().
By straightforward induction on the structure of , using the definitions of and . The only interesting case is when . Then we need to show () (). Using the definitions of and , we obtain () () () for the right-hand-side. By the definition of this is equivalent to () , which is equivalent to () by basic permutation group theory. Again by the definition of , this is equivalent to (), which we needed to show. The proof of () follows similar lines.
Extend notation for permutation actions and and substitution action to assertions and freshness contexts ∆in a pointwise fashion.
4.2. Inference rules.
Define derivability on freshnesses by:
Here Id, and and permutatively range over atoms, which means that they represent any two distinct atoms. Write ∆ # when # may be derived from ∆using the signature from T. Say that ∆ entails # in T.
Define derivability on equalities by:
Here (fr) is subject to a condition that ∆and the square brackets denote discharge of assumptions in natural deduction style [16].
Write ∆ when we may derive from ∆, using the signature from theory T and admitting only the axioms it contains. For any assertion , we may write as .
In (ax) the actions and make formal an intuition that in axioms we are supposed to permute atoms and instantiate unknowns. Take e.g. the theory () where stands for var( var(), for [][] , and for #[][]. Then these derivations
are valid taking ) and any , and ) and var() var()], respectively. But it is not possible to derive var( var() using () because no matter what we try to use, it must be bijective. Furthermore in
the left derivation is valid but the right one is not, because # is not derivable.
With reference to the discussion of versus above, another version of the rule (ax) is possible:
however in this case, atoms in the substitution are renamed according to . For example, from an axiom []] it is immediate that []] is derivable with (ax) where we choose ) and ]. It is also derivable with () but we must choose ) and ]. We find this version less natural.
Note that we assumed above that theories contain the axiom (perm); we could alternatively add () as a derivation rule.
We have not set up facilities to allow freshness axioms (ax). Such a thing is possible but we gain no expressivity; the same effect can be obtained by an equality axiom ∆## () where is fresh and are the unknowns mentioned in ∆and .
(fr) introduces a fresh atom into the derivation. To illustrate the extra power this gives, note that in a theory with an axiom #, we can derive with (fr), but cannot without it. (fr) guarantees that some atom fresh for exists. Further examples are derivations of [ var( and # ([]), which arise in the papers dedicated to the theories SUB [12, part 2 of Example 4.1] and FOL [13, 6th derivation of Figure 2].
Here are some derivations in CORE:
We may use () since [] () [] and []() () [].
As mentioned before, CORE is a theory of -equivalence — in the presence of meta-variables (represented by unknowns). It is an interesting algebraic version of work originally presented in nominal unification [27], and this can be made formal:
4.3. Proof theoretical results.
We naturally extend the meta-level action of permutations to theories: given a theory T Ax), write T for (Σ Ax ) such that ∆ Ax if and only if ∆ Ax.
If then .
By induction on derivations. The only nontrivial case is (ax), where we need to show that ∆ implies ∆ . By Lemma 4.3, this is equivalent to showing that
This follows by (ax) taking permutation and substitution .
If then .
By induction on the structure of derivations. We consider the most interesting cases only. Suppose the derivation of ∆ concludes in. . .
(1) (#X). Suppose # is derived from ()# using (#X), where Id. Then we need to show ()# (). By Lemma 4.1, this is equivalent to ()#() .
We continue by case distinction. Suppose Id. Then the proof obligation is equivalent to the assumption ()#, since by basic permutation group theory.1 The result follows.
Now suppose Id. Then by (#X) (which may now be applied), the proof obligation follows from ()-1(())#. Since we also have ()-1(((), this is equivalent to the assumption ()#, and again the result follows.
(2) (ax). Then is and ∆ .
We need to derive from ∆. By Lemma 4.2, this is equivalent to ()). By Lemma 4.4 it suffices to derive ((), where substitution maps each to . By Lemma 4.3, this is equivalent to ((). Then by (ax) with permutation and substitution , this follows from ∆(). Again by Lemmas 4.2, 4.4 and 4.3 this is equivalent to and we are done since by inductive hypothesis ∆ entails this.
(3) (fr). Then ∆## for some and we assume the inductive hypothesis of this derivation. If ( there is no problem since then and we may extend the derivation with (fr).
However, suppose () and so (possibly) . We observe that the predicate “if the labelled tree Π is a valid derivation of ∆ , then for all permutations there are derivations of ∆ ” has free variables Π, ∆, T, and .
We now use the principle of logical (FM) equivariance: if an assertion is true of some arguments, then it is also true of those arguments with some atoms permuted providing the axiom of choice is not used (in the cases we are interested in, it is not). For a proof of this beautiful and useful meta-principle see elsewhere [8, 15]. So the predicate above holds of Π, T, and and using Lemma 4.6 we deduce the inductive hypothesis of ∆## for any . Then ∆## and we extend the derivation with (fr) to deduce ∆ as required.
We may substitute terms for unknowns, provided the substitution on the freshness context is consistent:
If then for all such that .
We note that the structure of natural deduction derivations is such that the conclusion of one derivation may simply be ‘plugged in’ to an assumption in another derivation if assumption and conclusion are syntactically identical. We also note that the structure of all the rules except for (#X) is such that if unknowns are instantiated by , nothing need change. For the case of (#X) we use Theorem 4.7.
4.4. Soundness and completeness.
If then .
Let be a model of T. We work by induction on the derivation rules in Subsection 4.2. Most cases are very easy. We just give a sketch:
(#ab) is immediate, since by construction for any . (#f) follows because we assume f is equivariant. #[] is a basic property of nominal sets [15, Corollary 5.2] and (#[]a) follows. # if and only if #[], and # if and only if ()# are also basic properties, and (#[]b) and (#X) follow.
For (ax) suppose for any . Then ()#(()) holds for all # ∆. By logical equivariance then also #() for all # ∆where is defined as ((()) for all . So holds. Since ∆ is an axiom of T, also holds. Then follows by logical equivariance again.
Given a theory T we construct a term model of T as follows:
For each sort and 0 introduce a term-former d : ().
For each sort take as the set of closed terms of sort (terms without unknowns) in the enriched signature, quotiented by provable equality, with the permutation action given pointwise.
For each term-former f take as f the function defined as
We must enrich the signature with the d to ensure that our term model has enough elements. Since term-formers must be interpreted by equivariant functions, the usual method of adding constants c (0-ary term-formers) would add only elements such that c c always, which would not suffice. This idea goes back to [9].
It is not hard to prove the definition above well-defined, and that is an interpretation: that each is a nominal set, and that each f is equivariant.
If # then there is some such that #.
This result looks obvious, but it is not: let T have one base sort and one term-former : (). Let it have one axiom ((). It is easy to verify that #() but #() is not derivable. Of course, #() and (() are derivable.
Since # we do know that for fresh we have () that is () . Take () .
The term model of T is a model.
We show that if ∆ is an axiom of T then is valid for any . Let be the unknowns mentioned in ∆ and suppose that is such that #() for all # ∆. Use Lemma 4.10 to choose () such that # for each # Theorem 4.8 taking () we have that is derivable, because it is an instance of an axiom. By construction — is irrelevant on the right since is closed — and similarly So
If then .
By assumption we have for any model of T and any evaluation . Let be , the term model of T. In order to choose a suitable , we introduce the following:
Let be the set of atoms mentioned anywhere in ∆, , and .
Let be the set of unknowns mentioned anywhere in ∆, , or , (not just in ∆!) in some arbitrary order.
For each 1 let be the set of all atoms such that #
For each 1 let () d () where .
Assume the d we use are distinct; if necessary we ‘pad’ with extra fresh atoms, or use a richer term model with extra d.
Let map to () for 1 . By construction so by assumption and by definition this means that is derivable. This derivation can be transformed rule by rule into a derivation of ∆ , since the only freshnesses and equalities we can assert of the d are those we can also assert of the — the only complication is when perhaps for some fresh we use a freshness derivation to derive # for some fresh ; then we modify the derivation to use (fr) instead.
Completeness only holds for equalities, not freshnesses:
and # does not necessarily imply #. As a corollary # need not imply derivability of #.
A counterexample is the theory mentioned in Lemma 4.10.
So by Theorem 4.9 if # is derivable then # is valid, but the converse of Theorem 4.9 does not hold for freshness assertions. Recall that # when () To express this semantic notion we check derivability of ## () for some and the the unknowns in ∆ and . The complexity of deciding this depends on T, as it should.
5. Conclusions and related work
Nominal terms model the instantiation behaviour of meta-variables, e.g. in informal notation instantiating to in yields , reflected formally in this paper by the syntactic equality ([])[var()] []var(). NA stakes a claim to nominal terms as a logical system, and the support for binding allows us to reflect binding in logic in a direct fashion. Other work [12, 13, 11] demonstrates the flavour of nominal algebra applied to specific theories.
Nominal Algebra has similarities to Nominal Logic [23]: our () and (fr) correspond to axioms (F1) and (F4) of Nominal Logic. These come from the shared semantics in nominal sets, as ‘normal’ algebra shares a sets semantics with first-order logic. There are also significant differences. Nominal logic does not use nominal terms (they came later [26]) and freshness contexts, and this difference shows in the technical detail; for example the treatment of freshness in Nominal Logic is semantic in the sense of the discussion following Theorem 4.13 [23, p.175 ‘Freshness’].
Since the conception of Nominal Algebra, Pitts and Clouston have been developing ‘Nominal Equational Logic’ (publication in preparation at the time of writing). This seems closer than Nominal Algebra to being the pure equality fragment of Nominal Logic. In particular it features a semantic, not syntactic, treatment of freshness.
The theory of contexts [20] can be used to axiomatise systems with binding. So, differently, can higher-order algebra [19]. So indeed can simply-typed -calculus [22, Figures 6 and 7]. These systems are different and for different purposes but they share a core which is in essence simply-typed -terms up to -equivalence. As for nominal terms this richer term-language gives more expressivity which can be used to give stronger axioms. However, these approaches do not (so we argue) accurately capture our intention for the meta-variables and when we write ‘’ or ‘’; Nominal Algebra was designed with that in mind from the start. Also, moving to higher orders engenders certain computational difficulties [17].2 Still, quotienting terms by is convenient, as exploited by theorem-provers such as Isabelle — but this is not algebra for binding any more than quotienting arithmetic terms by arithmetic equality constitutes an algebra for arithmetic. Syntactic equivalence and provable equality — two quite different things!
Lambda-abstraction algebras [24] and cylindric algebras [5, 1] algebraically axiomatise systems with binding (-calculus and first-order predicate logic). They indirectly code freshness conditions; e.g. the use of throughout rule () just before definition 3 in [24, page 203] obtains the effect of ‘ is not free in ’. Likewise the use of throughout rule C4 in [5, page 29] in example 13 obtains the effect of ‘ not free in ’. In this connection we should also mention polyadic algebras; a brief but clear discussion of the design of these and related systems is in [4, Appendix C]. These systems are effective for their particular application but we see Nominal Algebra as parameterising the ‘binding’ part as an orthogonal structure (and of course in a new way involving the nominal terms). Sun has authored [25] a monumental study in doing just that; it is way ahead of us in terms of pure algebra.3 That work is be based on a functional semantics for binding [25, Definition 2.2.3], whereas we work according to the (relatively newer) nominal semantics, which is decidedly non-functional; currently the two strands are essentially independent and it remains to see what ideas might flow between them.
Combinators [3] make binding of variables ‘go away’. Algebras over (untyped) combinators can then express first-order predicate logic [2]. This interesting and difficult enterprise is more foundational/semantic than proof-theoretic/algebraic (the flavour of this work), because the extreme self-reflective power of untyped combinators makes contradictions hard to avoid.
References
[1] H. Andréka, I. Németi, and I. Sain. Algebraic logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 2, pages 133–249. Kluwer, 2001.
[2] H. Barendregt, W. Dekkers, and M. Bunder. Completeness of two systems of illative combinatory logic for first-order propositional and predicate calculus. Archive für Mathematische Logik, 37:327–341, 1998.
[3] H. P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.), volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1984.
[4] W. J. Blok and D. Pigozzi. Algebraizable logics. Memoirs of the A.M.S., 77(396), 1989.
[5] S. Burris and H. Sankappanavar. A Course in Universal Algebra. Springer, 1981. Available online.
[6] P. Cohn. Universal Algebra. Harper and Row, New York, 1965.
[7] M. Fernández and M. J. Gabbay. Nominal rewriting. Information and Computation, 2005. In press.
[8] M. J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.
[9] M. J. Gabbay. Fresh logic. Journal of Logic and Computation, 2006. In press.
[10] M. J. Gabbay and J. Cheney. A sequent calculus for nominal logic. In Proc. 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pages 139–148. IEEE Computer Society, 2004.
[11] M. J. Gabbay, A. Marin, and S. Rota Bulò. A nominal semantics for simple types. Submitted STACS’07, 2006.
[12] M. J. Gabbay and A. Mathijssen. Capture-avoiding substitution as a nominal algebra. In ICTAC’2006, 2006.
[13] M. J. Gabbay and A. Mathijssen. One-and-a-halfth-order logic. In PPDP ’06: Proceedings of the 8th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, pages 189–200, New York, NY, USA, 2006. ACM Press.
[14] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax involving binders. In 14th Annual Symposium on Logic in Computer Science, pages 214–224. IEEE Computer Society Press, Washington, 1999.
[15] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13(3–5):341–363, 2001.
[16] W. Hodges. Elementary predicate logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 1–131. Kluwer, 2001.
[17] D. Leivant. Higher order logic. In D. Gabbay, C. Hogger, and J. Robinson, editors, Handbook of Logic in Artificial Intelligence and Logic Programming, volume 2, pages 229–322. Oxford University Press, 1994.
[18] J. Loeckx, H. Ehrich, and M. Wolf. Specification of Abstract Data Types. Wiley, 1996.
[19] K. Meinke. Universal algebra in higher types. Theoretical Computer Science, 100(2):385–417, june 1992.
[20] M. Miculan. Developing (meta)theory of lambda-calculus in the theory of contexts. ENTCS, 1(58), 2001.
[21] D. Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Extensions of Logic Programming, 475:253–281, 1991.
[22] L. C. Paulson. The foundation of a generic theorem prover. Journal of Automated Reasoning, 5(3):363–397, 1989.
[23] A. M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186(2):165–193, 2003.
[24] A. Salibra. On the algebraic models of lambda calculus. Theoretical Computer Science, 249(1):197–240, 2000.
[25] Y. Sun. An algebraic generalization of frege structures - binding algebras. Theoretical Computer Science, 211:189–232, 1999.
[26] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. In CSL’03 & KGC, volume 2803 of LNCS, pages 513–527, 2003.
[27] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. Theoretical Computer Science, 323(1–3):473–497, 2004.
School of Mathematical and Computer Sciences, Heriot-Watt University, Edinburgh EH14 4AS, Scotland, Great Britain
E-mail address: murdoch.gabbay@gmail.com
Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
E-mail address: A.H.J.Mathijssen@tue.nl
Notes
1Composing both sides of Id with , we obtain . Inverting both sides, we obtain . ↩
2For example unification up to -equivalence is not decidable (restrictions of it are in [21]). Unification up to CORE is decidable [27]. ↩
3Ironically, this paper was published the same year as [14] and several other papers we know of on binding. ↩