Freshness and name-restriction in sets of traces with names
Murdoch J. Gabbay and Vincenzo Ciancia
Abstract. We use nominal sets (sets with names and binding) to define a framework for trace semantics with dynamic allocation of resources. Using novel constructions in nominal sets, including the technical devices of positive nominal sets and maximal planes, we define notions of capture-avoiding composition and name-restriction on sets of traces with names. We conclude with an extended version of Kleene algebras which summarises in axiomatic form the relevant properties of the constructions.
1 Introduction
Imagine a process evolving; every so often it may communicate with the outside world. In particular it may generate a new resource (allocate some memory; or perhaps create a cryptographic secret; or perhaps create a new channel name) and communicate that new resource.
Represent resources as atoms (set-theorists can think of urelemente; process-calculists can think of names). Then a model of the behaviour of our process is a trace (finite list of actions) that may contain atoms, and a model of the process is the set of all its possible traces. This is the trace semantics of computation [9], widely-used both in theory and application (e.g. the SPIN model-checker [17]).
Thus, a model of behaviour for processes with dynamic allocation, is sets of traces with atoms. But how then to represent dynamic allocation within this framework? After all, if a program outputs ab there is nothing in the string itself to tell us whether a, b, both a and b, or neither a nor b, has been ‘created fresh’.
We propose to represent binding using a notion similar to that of nominal abstract syntax [15]; if e.g. ab is a possible trace of the process then the a in that trace is considered -convertible when for all but finitely many , b is also in the set of possible traces of the process (note there is no binding primitive on the trace itself ).
We will develop a model of binding based purely on sets of traces, such that:
– There is an operation a that takes a behaviour (set of traces) X and creates another behaviour (also a set of traces) a.X in which a is -renameable.
– Union of sets of traces is exactly union of sets.
– There is a notion of capture-avoiding composition such that (a.X) b.Y a.b.(X Y) if we choose a fresh for Y and b fresh for X. Thus (a.ab) b.b a... Note that ab a.ab and b b.b but abb is not in their composition, because of capture-avoidance.
Finally we introduce axioms that regulate the behaviour of , by suggesting a notion of ‘nominal’ Kleene algebra [20].
We believe the constructions in this paper would be more generally applicable, so long as the semantics can be represented as sets and sensible notions of composition can be defined in some pointwise manner on their elements (in this paper it is sets of lists and list concatenation; see Definition 5.7).
Technical overview. The meat of this paper is some concrete calculations on nominal sets. The key technical facts are Theorems 3.14 and 3.16 and Proposition 4.6. The key definitions are Definitions 3.7, 4.5, and 5.7. The main theorem is Theorem 6.4.
Nominal sets were developed to represent syntax with binding; see [15] or a recent survey [13]. In this paper we use nominal sets to interpret sets of traces with atoms. The notions of names and free/bound names we use are exactly those from [15]; namely atoms and supporting set/freshness.
To the reader familiar with nominal sets, name-restriction a.X will be no surprise; Proposition 4.6 characterises it as a variation of atoms-abstraction [a]x from [15] (see [13, Definition 3.8 and Lemma 3.13]). Readers familiar with presheaves will recognise this as a sets-based presentation of from e.g. [8] or [21]; see [16,7] for further discussion.
The difference, which is significant, is that X and a.X are of the same type (both are sets of traces); our name-restriction is not a monad in the sense of [22], though it does a similar job. More on this in the Conclusions.
Given that behaviour is modelled as ‘just sets’ and not wrapped up in an explicit abstraction, the challenge is that in composition X Y, bound atoms in Y should somehow be detected and renamed to avoid capture with free atoms in X (see Remark 5.8), and vice-versa.
We use maximal positive planes as a foundational data structure for a notion of capture-avoiding language composition. Planes (Definition 3.3) are from [12] and were used to model capture-avoiding substitution. Positive planes are new (Definition 3.7), as is the connection with (Proposition 4.6). Arguably, planes and positive planes are as interesting as their application in this paper and we expect them to be useful in the future.
We conclude with an axiomatisation in the style of Kleene algebras and a proof of soundness (Section 6).
2 Nominal preliminaries
More on these constructions in [15] or in a recent survey [13].
Fix a countably infinite set of atoms. We use a permutative convention that a, b, c, . . . range over distinct atoms.
A permutation is a bijection on atoms such that nontriv(a (a) a is finite. We write id for the identity permutation such that id(a a for all a. We write for composition, so that ()(a((a)). We write for inverse, so that id . Write (a b) for the swapping permutation that maps a to b and b to a and all other c to themselves.
will range over permutations.
If A define fix(Aa A.(a a. A, B, C will range over finite sets of atoms.
A set with a permutation action is a pair X X, ) of an underlying set and a group action of permutations which we write x (so idx x and (x)x).
Say finite A supports x X when x x for all fix(A). Say x X has finite support when it is supported by some finite A.
A nominal set is a set with a permutation action whose every element has finite support. X will range over nominal sets and x will range over elements x X (that is, finitely-supported elements).
If , A are finite and support x then so does A.
Define supp(xA A finite and support x. Call supp(x) the support of x. Write a#x when a supp(x) and call a fresh for x.
We know supp(x) is well-defined in Definition 2.5 because by assumption at the end of Definition 2.3, x has some finite supporting set.
supp(x) supports x.
1. If (a a for all a supp(x) then x x.
2. If (a(a) for every a supp(x) then x x.
3. a#x if and only if b.b#x (b a)x x.
supp(xsupp(x).
Give X X a pointwise permutation action given by X x x X.
Define pow(X) to have elements X X with the pointwise permutation action and finite support.
It is not hard to use Proposition 2.8 to verify that pow(X) is a nominal set.
3 The planes of a set
From now until Section 6 we fix a nominal set X.
x, y, u, v will range over elements of X (i.e. x, y, u, zX) and X, Y, Z, U, and V will range over finitely-supported subsets of X (i.e. X, Y, Z, U, Vpow(X)).
3.1 Basic theory of planes
A subset X X can be represented as a not-necessarily-disjoint union of orbits under certain subgroups of the permutation action. A canonical representation can be created using planes (Definition 3.3). A plane is an -equivalence class of an element under simultaneous renaming of one or more of its atoms (cf. Lemma 3.2). For more on planes see [12, Subsection 3.3].
Define the plane x by x x fix(A). We may omit brackets, writing e.g. x for x and x for x.
If fix(A) then (x) x.
Lemma 3.2 expresses -convertibility for (x, A) as a choice of representative for the plane x, allowing us to rename supp(x)A. A plausible (if long) notation for x is (supp(x)A).x where is atoms-restriction (cf. Definition 4.5).
Suppose A is finite. Write u Z when u Z and for every and , u Z implies u. We call the plane u maximal in Z.
1. a (this is the only maximal plane in ).
2. aa(), (a, a)a(), and (a, b)a() (there are three maximal planes).
3. ab (this is the only maximal plane in b).
4. In Definition 3.3, quantification over is necessary. For example: a b, but for no a is ab (the only choice for is ).
For a fixed Z and u there may be two distinct subsets A supp(Z) and B supp(Z) such that u Z and u Z (thus; A and B are minimal but not least). For example, if Z (x, y) x a y b and u a, b) then u Z and u Z but u Z.
Z u u Z.
Planes in Z are ordered by subset inclusion. For each x Z, take some greatest element above x. Their union is Z.
3.2 Positive planes
For the definition see Definition 3.7 and Example 3.8.
Planes do not have to be disjoint. This may be a surprise at first, since planes are orbits of an element under a permutation group and we are used to results stating that orbits are either equal or disjoint—but the groups could be different for different planes. For example, (a, b) and (a, b) are both positive planes, but (a, b) (a, b) is non-empty because it contains (a, b).
Theorem 3.16 expresses that a union of positive planes behaves as a coproduct in one respect: if a plane is included in a union of positive planes, then it is included in one of the planes that made up that union.
Thus, the interest of positive planes is that they need not be disjoint, but when we take their union it behaves in some ways like a coproduct. This fails if planes are not positive; see Corollary 3.18 and Example 3.19. The importance of this will become more apparent in the next section.
a a is positive. a b is not.
If z x and A C then z x.
Suppose z x. Then z x for some fix(C) and fix(A). Now A C so fix(C) fix(A). By Lemma 3.2 (twice) z x x.
Suppose u and are positive. Suppose u .
Then u if and only if A.
Suppose x X and x and X are positive. Then there is A with x x X.
If x is positive then supp(x A.
If u Z and Z is positive then A supp(Z).
If Z is positive then supp(ZA u Z.
Theorem 3.14 fails if we remove the condition of maximality. For instance, supp( and a is non-maximal in for every a, but supp(aa and supp(a a .
Suppose I is some indexing set and for each i I, is a finite set of atoms and is some element. Suppose is positive for every i I and is finite. Then z implies z for some i.
We will show that C for some i I with z ; the result follows by Proposition 3.10. Suppose otherwise, so that i. zC. Choose some mapping ( ) C to fresh atoms. For each i there are two possibilities: if C then z and by Lemma 3.2 z ; if C then using Proposition 2.8 again z . Yet by construction fix(C) so z z, contradicting our assumption that z .
Suppose is positive for every i I, and is finite. Then z if and only if z for some i.
By Theorem 3.16 z for some i. We use maximality of z.
U ) (a, b) is not positive. U (a, b); then (a, b) is maximal in but is not a subset of U or (a, b). Thus, it is not possible to retrieve from a union of not-necessarily-positive planes a subcollection of planes that make up that union. Extending this paper to the ‘negative’ case is future work.
X is positive if and only if X for some set of positive such that is finite.
4 -restriction on nominal sets
We are now ready to define a notion of name-restriction on (positive) sets (Definition 4.5). By Theorem 3.16 the planes of a.U are ‘the planes of U, with a taken out of the support of each’. Proposition 4.6 relates that to a notion of ‘U, with a taken out of the support of U’ which resembles the nominal atoms-abstraction from [15] (see [13, Definition 3.8 and Lemma 3.13] for a proof). The rest of this section proves some useful equalities involving name-restriction.
(a). For comparison, (a)xx.
If B supp(X supp(X) then X X.
1. Suppose supp(u) B supp(u) A. Then u u.
2. Suppose X is positive. Then Xu u X.
If U is positive then a.U U.
If U is positive then so is a.U.
Suppose u and are positive. Suppose u .
Then u .
Suppose u . So there exists some fix() such that u . Also, by Proposition 3.10 A.
Consider some u u where fix(A a). Then u ), and fix(a).
We illustrate why positivity is necessary in Lemma 4.8. Note that a a b c but a b. However, b is not positive because c supp(bb.
Suppose U is positive. Then:
1. If ua.U then a and either u U or u U.
2. If u U then ua.U.
For positive U, supp(a.U supp(U) a.
Proposition 4.11 is not what it seems. To the reader familiar with nominal techniques it may look just like e.g. [15, Corollary 5.2] which is the corresponding result for [a]x.
But consider U ) (a, b). This has three maximal planes: (c, c), (c, b), and (a, c), and is not positive. Also supp(Ua, b, yet supp(a.U b. The reason for this ‘discrepancy’ is the observation made in the Introduction that a.U and U have the same type, whereas [a]U and U do not. Proposition 4.11 is different, and uses planes.
Suppose U is positive. Then a.U U if and only if a#U.
X X.
By routine properties of permutations, and Theorem 2.6.
Suppose U is positive. Then a.b.U b.a.U.
(XX).
As a corollary, if b#X then (b a)(Xb a)X) and a.X b.(b a)X.
5 Nominal languages
Write for the set of finite (possibly empty) strings of atoms.
k, l, m will range over elements of . We write kl for the concatenation of k and l. We write [] for the empty string.
is a nominal set with permutation action k () . . . () where is the ith element of k. Also, supp(k, . . . , (the atoms in k).
A nominal language is a positive subset of . , will range over languages.
An innocuous extension of Definition 5.1 is to use () for some .
Suppose is positive for every i I. Suppose supp() is finite. Then is positive. As a corollary, if and are languages then so is .
(a.) (a.a.().
acax xa and abax xa. An analogy with -terms: c.ac avoids name-clash with b whereas b.ab does not. Think of u in Definition 5.5 as . . . . .u where , . . . , supp(u) A. ‘Avoiding clash with S’ means choosing a representative u such that S for 1 i n. In Definition 5.7, the superscript supp() and supp() supp(k) are generalised capture-avoidance conditions. More on this in Remark 5.8.
Recall that here, kl denotes list concatenation. In words: is a capture-avoiding composition of the maximal planes of and . For example, if a and then we can take k a, A a, l b and B to calculate that ax xa ab.
The ‘definition’ kl k, l would put the string aba in (b.ab) b.b. This is undesired behaviour because b.b should avoid clash with the name a free in b.ab. Similarly the ‘ordinary’ notion of composition kl k , l does not avoid capture and delivers incorrect results.
The mention of supp(k) in l tells l to avoid name-clash with atoms used in k; if we wrote l then composition would deallocate fresh names in k before executing l. Thus, Definition 5.7 does not put abb in (b.ab) (b.b), because of the mention of supp(k).
is positive.
1. If a# then (a.) a.().
2. If b# then b.b.().
Suppose and are languages. Suppose supp() supp() C. Then kl k, l.
() ().
Set C supp() supp() supp(). It is a fact that supp() C and supp() C.3
By Corollary 3.18 and Lemma 5.12 if n () then n m for some and some m M. Similarly, kl for some k and l.
By renaming k and l appropriately we may assume that kl. It is a fact that supp( supp(k) supp(l). It follows that
() M klm k, l, m.
The result follows.
If supp() is finite then () and () ().
We consider only the first part; the proof of the second part is similar. Set G supp() supp(). We prove two subset inclusions.
– Proof of the left-to-right subset inclusion. Choose some k. Suppose n. From Theorem 3.16 n for some i. By Lemma 5.12 kn().
– Proof of the right-to-left subset inclusion. Suppose n(). By Lemma 5.12 we may take n kl and D A B for some k and some i and l. Using Corollary 3.11 we can deduce that l l for some B. Since A A B we can conclude that n kl.
Define (the empty set). Define [] (recall from Definition 5.1 that [] is the empty string).
and .
and are languages. Also, the set of languages is closed under , a., , and .
6 Nominal Kleene algebra
We can use a nominal algebra style axiomatisation [14] to synthesise what we have proved so far as an extension of Kleene algebras (Definition 6.2 and Theorem 6.4). ‘Nominal Kleene algebra’ should be read tongue-in-cheek; we have no completeness proof like [20]. This is future work.
Call x X equivariant when supp(x, thus .x x.
Call a function f XY equivariant when f (x f (x) for all x X and all permutations .
A nominal Kleene algebra is a tuple , , , , 0, 1, ) of:
– A nominal carrier set .
– Equivariant functions and from to . We usually omit , writing e.g. XY for X Y.
– An equivariant function from to .
– Equivariant elements 0 and 1 .
– An equivariant function from to .
such that for all X, Y, Z and all a, b the conditions in Figure 1 hold.
The upper axioms are the standard axioms of a Kleene algebra [20]. Here (as standard) we write r s as shorthand for r s s. Note that these axioms are not purely equational (so Kleene algebra is not, depending on terminology, actually algebraic), and the class of Kleene algebras forms a quasi-variety. This will not matter to us in this paper.
The axioms on the lower lines describe behaviour of name-restriction.
Note that a.0 0 and a.1 1 follow from the axiom a#X a.X X, because it is a fact that a#0 and a#1.
Languages form a nominal Kleene algebra if we interpret as , as , as , and 0 and 1 as and respectively.
We consider each axiom in turn:
– It is a fact that () , and . It is also a fact that and .
– () by Lemma 5.13.
– () () and () ) () are by Theorem 5.14.
– and by Lemma 5.17.
– The four axioms for follow using Theorem 5.14. To use some jargon, our denotation is -continuous [19].
– If a# then a. is by Corollary 4.13.
– (a.) (a.a.() is by Theorem 5.4.
– (a.) (a.a.() is by Theorem 5.11.
– a.b.b.a. is by Corollary 4.15.
– b#a.b.(b a) is by Proposition 4.16.
7 L ◦ is equal to
Nominal sets have an atoms tensor product X ([27] or [13, Definition 9.27]) given by X (x, a) x X, a , a#x. This has an obvious generalisation: X Y (x, y) x X, y Y, supp(x) supp(y. We can view as another (less obvious) generalisation of , as follows:
If supp( then and , where we treat as a nominal set with underlying set itself.
Thus, composition of languages generalises . - is left-adjoint to atoms-abstraction []- [13, Theorem 9.30]. By Proposition 7.1, so is - . It remains to investigate the futher properties of - .
8 Conclusions
Name-generation has long been a motivation for nominal techniques.
Odersky in [24] and Pitts and Stark [25] studied name-generation, and this was in the background thinking of the first author’s and Pitts’s development of Fraenkel-Mostowski/nominal sets. FreshML included a name-generating construct [29] which was a precursor of Fernández and the first author augmenting nominal terms and nominal rewriting explicitly with name generation a.t [5]; Pitts added a similar construct a.t to system T [26]. The axioms for a in Figure 1 are of the same family.
A very abstract semantic study of name-generation is the abstractive functions considered in [11]. This influenced [12], where much machinery used in this paper was introduced. Abramski et al. give a concrete games semantics to the nu-calculus in nominal sets [1]: ideas here and in [12] also appear there, including Definition 3.1 (see e.g. Definition 2.7 of [30]).
There exist denotations for dynamic allocation using atoms-abstraction []-, typically written in presheaf presentations. Examples are coalgebraic semantics for the -calculus using (see e.g. [6, Subsection 2.2] or [2, Subsection 5.2]), the name-generation monad of FreshML [28, F, page 38]. We can also include the XY construct of nominal games from [1], which is in the same spirit and used in similar ways. In these examples name-generation exists at its own distinct level; in programming terms this corresponds to carrying around an explicit context of known ‘fresh’ names.
a (Definition 4.5) is different because it places binding on a level with union and composition : a language is just a set of traces, not under a monad and not a set of -equivalence classes of sets of traces. Thus we must work harder because freshness must be ‘decrypted’, but this buys us an appealingly simple model. A language really is just a set—as in the classical case of regular languages, without names and binding. That explicit context of known ‘fresh’ names is not explicitly necessary in the mathematical models we build.
One can raise the question of decidability of equality and inclusion between (subclasses of) languages, and automata. To consider such questions we need to match the developments of this paper with an automata-theoretic counterpart.
One well-studied notion of finite automaton with names and allocation is history-dependent (HD-)automata [23]. The correspondence to coalgebras over presheaves/nominal sets is considered in [3]. Investigation of the languages of HD-automata and the link with finite-memory automata [18] has shown that HD-automata are still essentially finite-memory machines [4]. However, the finite-support property of nominal sets corresponds to an idea of ‘finitely but unboundedly many’. In FreshML, a type system in [10] first tried to restrict generation of fresh names and later in [28] the programming language appeared without such restrictions but the denotation used a monad to keep track of generated fresh names. Similarly, we would expect acceptors for languages from Section 5 to either impose bounds on support (if they are to be finite), or to be in the style of e.g. pushdown automata.
Most recently, fresh register automata have also been proposed, explicitly as an automaton model of names and fresh name generation [31]. It remains to investigate these in connection with this work.
We note in Remark 5.9 a ‘deallocating’ variant of composition . There is a rich design space here to be studied in future work.
Nominal sets have further structure. We can model when a process omits a name (e.g. ‘junk’ in the -calculus; a channel name that is not emitted yet occurs in the syntax of the term) using a freshness constraint: X#x X a#X.
Note that is not the -quantifier introduced by the first author with Pitts in [15]. For instance, X a.X is a fact, whereas (x) x.(x) is in general false. It is possible to define a version of acting on languages, given by na.X x X b.(b a)x X. We do not believe that n and are interdefinable and investigating them is future work.
Our models do not include negation; this is also future work.
Acknowledgements. Thanks to Emilio Tuosto and three anonymous referees. Supported by VICI grant 639.073.501 of the NWO and grant RYC-2006-002131 at the Polytechnic University of Madrid.
References
1. Samson Abramsky, Dan R. Ghica, Andrzej S. Murawski, C.-H. Luke Ong, and Ian D. B. Stark, Nominal games and full abstraction for the nu-calculus, Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), IEEE Computer Society Press, 2004, pp. 150–159.
2. Marcello Bonsangue and Alexander Kurz, Pi-calculus in logical form, Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), IEEE Computer Society Press, 2007, pp. 303–312.
3. Vincenzo Ciancia and Ugo Montanari, Symmetries, local names and dynamic (de)-allocation of names, Information and Computation (2010), In press.
4. Vincenzo Ciancia and Emilio Tuosto, A novel class of automata for languages on infinite alphabets, Tech. Report CS-09-003, University of Leicester, UK, 2009.
5. Maribel Fernández and Murdoch J. Gabbay, Nominal rewriting with name generation: abstraction vs. locality, Proceedings of the 7th ACM SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP 2005), ACM Press, July 2005, pp. 47–58.
6. Marcelo Fiore, Eugenio Moggi, and Davide Sangiorgi, A fully-abstract model for the -calculus (extended abstract), Proceedings of the 11th IEEE Symposium on Logic in Computer Science (LICS 1996), IEEE Computer Society Press, 1996, pp. 43–54.
7. Marcelo Fiore and Sam Staton, Comparing operational models of name-passing process calculi, Information and Computation 204 (2006), no. 4, 524–560.
8. Marcelo Fiore and Daniele Turi, Semantics of name and value passing, Proceedings of the 16th IEEE Symposium on Logic in Computer Science (LICS 2001), IEEE Computer Society Press, 2001, pp. 93–104.
9. Nissim Francez, C. A. R. Hoare, Daniel J. Lehmann, and Willem P. de Roever, Semantics of nondeterminism, concurrency, and communication, Journal of Computer and System Sciences 19 (1979), no. 3, 290–308.
10. Murdoch J. Gabbay, A Theory of Inductive Definitions with alpha-Equivalence, Ph.D. thesis, University of Cambridge, UK, March 2001.
11., A General Mathematics of Names, Information and Computation 205 (2007), no. 7, 982– 1011.
12., A study of substitution, using nominal techniques and Fraenkel-Mostowski sets, Theoretical Computer Science 410 (2009), no. 12-13, 1159–1189.
13., Foundations of nominal techniques: logic and semantics of variables in abstract syntax, Bulletin of Symbolic Logic (2010), In press.
14. Murdoch J. Gabbay and Aad Mathijssen, Nominal universal algebra: equational logic with names and binding, Journal of Logic and Computation 19 (2009), no. 6, 1455–1508.
15. Murdoch J. Gabbay and Andrew M. Pitts, A New Approach to Abstract Syntax with Variable Binding, Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.
16. Fabio Gadducci, Marino Miculan, and Ugo Montanari, About permutation algebras, (pre)sheaves and named sets, Higher-Order and Symbolic Computation 19 (2006), no. 2-3, 283–304.
17. Gerard J. Holzmann, The spin model checker: Primer and reference manual, Addison-Wesley Professional, September 2003.
18. Michael Kaminski and Nissim Francez, Finite-memory automata, Theoretical Computer Science 134 (1994), no. 2, 329363.
19. Dexter Kozen, On induction vs. -continuity, Proceedings of the Logic of Programs Workshop, Lecture notes in computer science, vol. 131, Springer, 1982, pp. 167–176.
20. Dexter Kozen, A completeness theorem for Kleene algebras and the algebra of regular events, Information and Computation 110 (1994), no. 2, 366390.
21. Marino Miculan and Ivan Scagnetto, A framework for typed HOAS and semantics, Principles and Practice of Declarative Programming, 5th International ACM SIGPLAN Symposium (PPDP 2003), ACM, 2003, pp. 184–194.
22. Eugenio Moggi, Notions of computation and monads, Information and Computation 93 (1991), no. 1, 55–92.
23. Ugo Montanari and Marco Pistore, Pi-calculus, structured coalgebras and minimal hd-automata, MFCS 2000 (Mogens Nielsen and Branislav Roman, eds.), Lecture Notes in Computer Science, no. 1983, Springer, 2000.
24. Martin Odersky, A functional theory of local names, Proceedings of the 21st Annual ACM Symposium on Principles of Programming Languages (POPL’94), ACM Press, 1994, p. 4859.
25. A. M. Pitts and I. D. B. Stark, Observable properties of higher order functions that dynamically create local names, or: What’s new?, Proceedings of the 18th International Symposium on Mathematical Foundations of Computer Science (MFCS 1993), Lecture Notes in Computer Science, vol. 711, Springer, 1993, pp. 122–141.
26. Andrew M. Pitts, Nominal system T, Proceedings of the 37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2010), ACM Press, January 2010, pp. 159–170.
27. Andrew M. Pitts and Murdoch J. Gabbay, A Metalanguage for Programming with Bound Names Modulo Renaming, Proceedings of the 5th international conference on the mathematics of program construction (MPC 2000), Lecture Notes in Computer Science, vol. 1837, Springer, December 2000, pp. 230–255.
28. Mark R. Shinwell and Andrew M. Pitts, On a monadic semantics for freshness, Theoretical Computer Science 342 (2005), no. 1, 28–55.
29. Mark R. Shinwell, Andrew M. Pitts, and Murdoch J. Gabbay, FreshML: Programming with Binders Made Simple, Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), vol. 38, ACM Press, August 2003, pp. 263–274.
30. Nikos Tzevelekos, Nominal game semantics, Ph.D. thesis, Oxford, 2008.
31., Fresh-register automata, Proceedings of the 38th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2011), ACM Press, January 2011.
Notes
1 Positivity is sufficent but not necessary. It suffices to restrict to u such that (supp(u) A). This excludes an artefact of representing planes as pairs (u, A) since if supp(u) A and supp(u) B then u u u. Since we concentrate on positive planes, where this cannot happen, we can ignore this. ↩
2 Contrast with ab b a b b. Theorem 3.16 is inapplicable because supp(b) b a is not finite. ↩
3 We can deduce this by direct calculations or by construction and using Theorem 3.14. ↩