Nominal SOS
Abstract
Plotkin’s style of Structural Operational Semantics (SOS) has become a de facto standard in giving operational semantics to formalisms and process calculi. In many such formalisms and calculi, the concepts of names, variables and binders are essential ingredients. In this paper, we propose a formal framework for dealing with names in SOS. The framework is based on the Nominal Logic of Gabbay and Pitts and hence is called Nominal SOS. We define nominal bisimilarity, an adaptation of the notion of bisimilarity that is aware of binding. We provide evidence of the expressiveness of the framework by formulating the early -calculus and Abramsky’s lazy -calculus within Nominal SOS. For both calculi we establish the operational correspondence with the original calculi. Moreover, in the context of the -calculus, we prove that nominal bisimilarity coincides with Sangiorgi’s open bisimilarity and in the context of the -calculus we prove that nominal bisimilarity coincides with Abramsky’s applicative bisimilarity.
Keywords: SOS, Nominal SOS, Nominal calculi, -calculus, -calculus.
1 Introduction
The development of a formal semantics for programming and specification languages is a necessary first step towards rigorous reasoning about them. For instance, a formal semantics allows one to prove the correctness of language implementations, and is a prerequisite for proving the validity of program optimizations. Operational semantics is a widely-used methodology to define formal semantics for computer languages, which represents the execution of programs as step-by-step development of an abstract machine. Structural Operational Semantics (SOS) was introduced by Gordon Plotkin in [24], reprinted in [25], as a logical and structural approach to defining operational semantics. The logical structure of SOS specifications supports a variety of reasoning principles that can be used to prove properties of programs whose semantics is given using SOS. Moreover, SOS language specifications can be used for rapid prototyping of language designs and to provide experimental implementations of computer languages.
SOS has become the de facto standard for defining operational semantics, and a wealth of programming and executable specification languages have been given formal semantics using it. In recent years much work on the underlying theory as well as on the practice of SOS has been carried out—see, e.g., [3,21] and [6,13,20], respectively. Many programming and specification languages make use of the concepts of names and binders. For example, in the -calculus [18,19,29], names are first-class objects and the whole language is built on the idea that concurrent agents communicate by exchanging names. Incorporating nominal notions within SOS has received some attention in recent years, but nevertheless the meta-theory of SOS is not sufficiently adapted for these new frameworks. In this paper we propose a formal framework for the handling of names in SOS, called Nominal SOS, which is based on the nominal techniques of Gabbay, Pitts, and Urban [11,31].
The most important notion of equivalence of programs in the context of SOS is bisimilarity [22]. We argue that this notion, taken as it is, is not satisfactory and we adapt bisimilarity in order to better suit our context with binders. We call this equivalence nominal bisimilarity.
Basic notions such as -conversion and substitution are essential parts of most nominal calculi. We show that these notions can be naturally captured in the Nominal SOS framework. Moreover, we give evidence of the expressiveness of our framework by modeling two of the most prominent examples of nominal calculi, namely the lazy -calculus and the early -calculus. For both we show that our specifications coincide operationally with the original definitions of [2] and [29], respectively. We moreover prove that in the case of the -calculus our notion of nominal bisimilarity coincides with the well-known open bisimilarity of Sangiorgi [29,28]. Finally, we show that nominal bisimilarity in the context of our formulation of the lazy -calculus coincides with the applicative bisimilarity of Abramsky [2].
Proofs are omitted in the main text and the reader can find them, together with a fully elaborated account of Nominal SOS, in [8]. This document extends the last chapter of Cimini’s Ph.D. thesis [7]. Structure of the paper. The rest of the paper is organized as follows. In Section 2 we define nominal terms and in Section 3 we define the framework of Nominal SOS. We show in Section 4 how -conversion and different types of substitution can be accommodated in Nominal SOS. Section 5.1 is devoted to our formulation of the -calculus and Section 5.2 addresses the lazy -calculus. In Section 6 we discuss related work and Section 7 concludes the paper.
2 Nominal terms
The following definitions of sorts and nominal signature are familiar from [31].
(Sorts) Sorts are defined inductively by the following grammar:
where 1 is the unit sort, is a base sort, is an atom sort, [] denotes an abstraction sort, and denotes pairing.
Intuitively, [] is a sort whose elements are functions from objects of sort to objects of sort . As is standard, pair sorts will associate to the left, so that stands for () .
(Nominal signature) A nominal signature Σ is a triple ), where
is a set of base sorts ranged over by ,
(ii) is a set of atom sorts ranged over by , and
(iii) is a set of operators , denoting a function symbol with arity () , where 0.
For each atom sort , we fix a countably infinite set of atoms , , , . . . , and for each sort , we assume a countably infinite set of variable symbols , , . . . . We sometimes write just , , and , leaving arities and sorts implicit (but still present). We assume that all these sets of symbols are pairwise disjoint.
(Nominal terms) Given a signature ), the set of nominal terms over the signature Σ is denoted by (Σ) and it is defined as follows, where we write for a term of sort :
where , , and with arity () .
The subscripts of nominal terms control sorting and we tend to omit them when they are clear from the context or immaterial. We call [] an abstraction. We have not introduced any means to introduce pairs of terms, as we only use product sorts to give a sort to transition relations (see Section 3).
For a nominal term , the following definitions will be useful in the remainder of the paper. In what follows, and are a unary and a binary function symbol.
() stands for the set of atoms that occur in . For example, (([]( .
ba() is the set of atoms for which there exists a subterm [] in , i.e., the set of abstracted atoms in . For example, ba(([](.
fa() is the set of atoms in () that have an occurrence in that is not within the scope of an abstraction [], for some term . We call fa() the set of free atoms of . For example, fa(([]( and also fa((([]).
An atom is fresh in whenever fa(). We also say that a term is binding-closed if fa(, i.e., the term does not contain free atoms. 1
We say that a nominal term is closed if it contains no variables. It is called open otherwise. For example, and []() are closed terms, but and [] are open terms. Note that neither nor []() is binding-closed.
3 Nominal SOS
Suppose is an atom and is a term of some sort. We call a formula # a freshness assertion. In what follows we give a derivation system in order to derive freshness assertions.
(Freshness derivation rules) Let Σ be a nominal signature, and let the atom and the term be over the signature Σ. We say that # is derivable when it may be derived using the following rules, where and are distinct atoms.
These derivation rules are familiar from existing work [31,9].
We are now ready to define the notion of nominal transition system specification whose rules employ the freshness assertions defined above.
(Nominal Transition System Specification) A nominal transition system specification ( NTSS) is a triple (Σ) consisting of:
(i) A nominal signature Σ;
(ii) A set of (transition) relation symbols . To each we associate a (transition relation) arity which is a sort of the form . We may call: the ‘sort of the source of the transition’, the ‘sort of the target of the transition’, and the ‘sort of the label of the transition’.
(iii) A set of derivation rules (see below).
Given an NTSS , we denote with () the set of atoms of the signature of . For a relation with arity , if is the unit sort 1 then we say that has no label. If is also the unit sort, then is a predicate symbol. We may silently drop (and ) if they are the unit sort.
For a relation with arity , a positive transition formula is written , where is a possibly open term of sort (we call it the source term), is a possibly open term of sort (we call it the label), and is a possibly open term of sort (we call it the target term).
For the same relation , we write for a negative transition formula, where is of sort and is of sort . A transition formula is a positive or negative transition formula.
(Derivation rule) A derivation rule is of the form
where
, and are indexing sets,
is a set of positive transition formulae, called the positive premises of the rule,
is a set of negative transition formulae, called the negative premises of the rule,
# is a set of freshness assertions, called the freshness premises of the rule, and
is a positive transition formula, called the conclusion of the rule.
We call , , and the source, the label and the target of the rule, respectively.
We call a derivation rule an axiom if , and are empty. A derivation rule is positive when the index set is empty. An NTSS is positive when all its deduction rules are positive. Positive NTSS’s come with a natural notion of semantics, i.e., the set of provable closed transitions formulae; the same notion is adopted for the semantics of freshness formulae by means of the derivation rules given in Definition 3.1. In this paper we restrict ourselves to positive NTSS’s; the semantics of full Nominal SOS can be found in [7, Section 5.3.1].
The most important notion of equivalence between programs defined in SOS is bisimilarity [17,22]. Unfortunately, this equivalence turns out not to be satisfactory in a context with binders. This point is carefully explained, in the context of the -calculus, on pages 64-65 of [29], where it is shown that the two processes and () are distinguished since can perform a transition while is not able to perform any transitions; the reason is that is not able to change its bound variable to since is not fresh in .
Nominal bisimilarity is thus introduced below as an adaptation of the ordinary bisimilarity that is aware of binding. What happens in the theory of the -calculus is that bisimilarity is adjusted and transitions of the form are matched only for those bound variables that are fresh in both terms. Our notion of bisimilarity revisits the ordinary bisimilarity in such a manner. In the remainder of the paper we will relate nominal bisimilarity to important notions of equivalence in the literature.
(Nominal bisimilarity) Let be an NTSS. Nominal bisimilarity –– is the largest symmetric binary relation over closed terms of such that for all closed terms and and labels such that and # and # for all ba(), it holds that if then there exists such that and .
4 Substitution and -conversion
4.1 Substitution transitions
Substitution and -equivalence play a key role in the definition of the semantics of calculi with binders. We will now show how those notions can be accommodated in a uniform fashion within the framework of Nominal SOS.
Term-for-atom substitutions are typically employed by higher-order calculi, such as the -calculus, the Calculus of Higher Order Communicating Systems (CHOCS) [30] and the Higher-Order -calculus [26], just to mention a few. Given a nominal signature, we proceed to generate the following types of deduction rules with the
goal of proving transitions of the form for some atom and terms , and . This type of transition should be read as the term replaces the atom in the term leading to the term . For all atoms and function symbols , we have the following rules.
The reader can infer the sort of the variables used in the rules by their usage. In the rules above we use variables of atom sort whenever possible with the exception of rule (1Ts) that would appear less readable. The reader may be more familiar with the syntactic substitution operation, defined below, where and are closed terms and and are distinct atoms.
([])[]([]) if is fresh in
The following theorem states that the two notions (substitution transitions and syntactic substitutions) correspond 2 .
(Correctness of Substitution Transitions) Let be an NTSS.
Let and be closed terms, and be an atom. Then, it holds that if and only if [].
Atom-for-atom substitution is used in calculi such as the -calculus [29,19] and its variants. The same set of rules provided for the term-for-atom substitution are able to model the atom-for-atom substitution. These transitions are denoted and the first and second argument of this label range over atoms.
A syntactic atom-for-atom substitution over nominal terms, together with its corresponding correctness theorem, can be provided. It turns out to be just a straightforward adaptation of Theorem 4.1.
4.2 -conversion Transitions
The notion of -conversion is a natural equivalence guaranteeing that the exact atom chosen in binders is not important and can be indeed replaced by any other atom (while avoiding capture). Thanks to freshness assertions, we can accommodate -conversion in our framework as an ordinary transition relation. Given a nominal signature, the following deduction rules define . For all atoms and and function symbols , we have the following rules. 3
The reader will notice that -conversion transitions rely on those for the atom-for-atom substitution (rule (1)). Throughout the paper, whenever we say that the rules above for -conversion transitions are present in an NTSS, this implies that also the rules for atom-for-atom substitutions are present.
The reader is perhaps familiar with the syntactic version of -conversion, defined below.
(-conversion over nominal terms) Let be an NTSS. The relation is the least congruence on nominal terms over the signature of , such that, for all closed term and an atom , if is fresh in then [] [][].
The set of rules for -conversion transitions generated above actually behaves ac-cording to the syntactic -conversion, as stated in the following theorem 4 .
(Correctness of -conversion transitions) Let be an NTSS. For all closed terms and over the signature of , it holds that if and only if .
Calculi with binders usually consider a term as a representative of the equivalence class of all the terms that are -convertible to it. In Nominal SOS, it is possible to achieve this by augmenting the NTSS with a deduction rule, given below.
(Transitions up to -equivalence) Let be an NTSS and be a label of the signature of . The transition relation is up to -equivalence whenever the deduction rules of contain the rules for -conversion transitions, as defined above, the rules for atom-for-atom substitution transitions, as defined in Section 4.1, and the deduction rule:
Depending on the peculiarities of the calculus at hand, the modeller might want to consider defining some of the transition relations to be up to -equivalence.
5 Examples
In this section we provide some evidence of the expressiveness, and perhaps natural-ness, of Nominal SOS by formulating in our framework two classical calculi, namely the early -calculus [29,19] and the lazy -calculus [2].
5.1 The early -calculus and open bisimilarity
The signature Σ of our -calculus is modelled by a base sort and atom sort (for processes and channels, respectively) and the following function symbols.
(i) 0 : for inaction (deadlock),
(ii) : for -prefix,
(iii) ( ) : () for output prefix,
(iv) ( ) : ( []) for input prefix,
(v) ( ) : [] for restriction,
(vi) : () for parallel composition,
(vii) : () for nondeterministic choice,
(viii) ! : for parallel replication.
The syntax employed for input and output prefixes differs slightly from the standard notation used in the -calculus. In particular, our term () corresponds to the process of the -calculus, and ( []) corresponds to (). The same choice is adopted for the labels.
Below, we specify the semantics of the early -calculus in Nominal SOS. Since in our framework labels are open terms, we display an input transition label as (), assuming a different operator accepting two atoms as arguments. For presenta-tional purposes, we use the same names to stipulate the meaning of the transitions. For the same reasons, we model an output transition label as () and a bound output transition label as ( []0), abbreviated as ( []) throughout the text. The set of rules of the signature Σ contains the following rules, we use to range over labels and , and to range over atoms.
For the sake of brevity, we omit the symmetric versions of rules (sum1), (par1), (parRes1), (com1) and (close1). Moreover, for each label , is up to -equivalence. Following the recipe of Definition 4.4 we add to our NTSS the set of rules for -conversion transitions and the rules for atom-for-atom substitution transitions. We set the atom-for-atom transition relations to be up to -equivalence, too.
The reader must notice that the complicated side-conditions of the ordinary formulation of -calculus are here replaced by rather simpler freshness conditions, see rules (parRes1) and (close1).
We denote by Π the set of -terms of [29]. The encoding is a map from Π into terms of our nominal -calculus. The mapping is straightforward and its definition is omitted here; it can however be found in [8]. 5 The following theorem establishes that our formulation of the early -calculus is operationally correct with respect to its original formulation 6 .
(Operational Correspondence: early -calculus) For all Π, , where ranges over the labels of the form , , and () from the original early -calculus.
The reader may wonder what is the equivalence over -calculus terms that corresponds to nominal bisimilarity. The next theorem provides us with an answer: nominal bisimilarity in our formulation of the early -calculus coincides with Sangiorgi’s open bisimilarity, see [29, Section 4.2] and [28].
(Open bisimilarity) Open bisimilarity is the largest symmetric relation on Π such that whenever , and is a substitution (see Definition 1.1.3 on page 14 of [29]), if , then there exists , such that and .
The reader should notice that this definition is the very basic formulation of open bisimilarity, which does not involve distinctions, see [29] and [28]. In Definition 5.2, it is important to note that the ranging over all the substitutions is performed at each step of the bisimulation game.
(Open bisimilarity and Bisimilarity coincide) For all Π, if, and only if, –– .
Theorem 5.3 essentially holds because in our nominal formulation of the -calculus, nominal bisimilarity also takes into account the substitutions transitions 7 . In [7, Section 5.21], it is shown that if nominal bisimilarity is adapted not to match the substitution transitions it would coincide with the ordinary bisimilarity over the -calculus.
5.2 The lazy -Calculus and applicative bisimilarity
The signature Σ of the lazy -calculus is constructed using a base sort for -terms and an atom sort . The signature also contains the following function symbols.
(i) : : A unary function symbol for creating terms from atoms;
(ii) ( ) : []: A unary function symbol for abstractions;
(iii) : () : A binary function symbol for application.
The semantics includes a reduction transition , here displayed with no label to remain in line with the standard notation from [2], transitions for terms of sort , and the rules for term-for-atom substitution transitions as generated in Section 4.1, but where rules (1Ts) and (2Ts) are modified to deal with embedding
of atoms. For instance, rule (1Ts) becomes () .
The set of rules of the signature Σ contains the following derivation rules, which define the operational semantics of our version of the lazy -calculus, for all atoms .
(abs1AP)
Moreover, the transition relations , for any binding-closed term and the term-for-atom substitution transitions are up to -equivalence. Recall that, by Definition 4.4, this means that the set of rules of Σ contains also the rules for -conversion transitions and the rules for atom-for-atom substitution transitions. Rules (1Ts) and (2Ts) are modified as before also for atom-for-atom substitution transitions and these transitions are set to be up to -equivalence.
We denote by Λ the set of -terms of [2,4], and by Λ0 the set of those that do not contain free variables. The encoding is a map from Λ into terms of our nominal -calculus. The mapping is straightforward and not presented here; it can however be found in [8]. 9 The following theorem establishes the operational correctness of our formulation of the lazy -calculus with respect to its original formulation for -terms in Λ0 10 .
(Operational Correspondence: lazy -calculus) For all Λ0, .
The reader should notice that if we ruled out the premises (#) from rule (abs2AP) the operational correspondence of Theorem 5.4 would hold for the set of all -terms. The reason we restrict the parameter passing to binding-closed terms only is that it ties up directly with the study that follows.
In the context of the lazy -calculus, one of the most interesting notions of bisimilarity is the applicative bisimilarity due to Samson Abramsky [2]. Below we recall the definition of this equivalence.
(Applicative bisimilarity in the -calculus) Applicative bisimilarity is the largest symmetric relation on Λ0 such that whenever , if for some variable and Λ, then there exist some variable and Λ such that
, and
[] [], for all Λ0.
It is important to remark that the applicative bisimilarity of the -calculus is defined over closed -terms. Indeed, this equivalence is very unsatisfactory over terms that contain free variables. For instance, for all variables , and , it holds that and .
The following theorem states that applicative bisimilarity in the lazy -calculus coincides with nominal bisimilarity in the nominal formulation of the lazy -calculus given above 11 .
(Applicative and Nominal Bisimilarity coincide) For all Λ0, if, and only if, –– .
6 Related Work
We are aware of a number of existing approaches that accommodate names and binders inside the SOS framework. The frameworks that are most relevant to the work presented in this paper are by Miller and Tiu in [16] (), by Lakin and Pitts in [15] (MLSOS) and in [14] (ML) and by Gacek, Miller and Nadathur in
[12] (Abella).
As a first difference, Nominal SOS is the only approach that directly extends the formal framework of SOS. We identify some benefits supporting this choice. First, users that are familiar with the SOS framework will find Nominal SOS easy to use. Secondly, although a meta-theory of SOS for calculi with binders can be carried out with the frameworks mentioned above, Nominal SOS seems to be close enough to ordinary SOS. In this respect, a meta-theory for binders can follow by and large the same lines of the meta-theory of ordinary SOS, which has been successfully developed for over 20 years, see [21]. We also expect that already existing results from the meta-theory of SOS would lift to Nominal SOS with relatively little effort.
Some technical differences between Nominal SOS and the systems mentioned above are worth a mention. For instance in MLSOS and -ML, only restricted op-erations are allowed on atoms and programs do not depend upon concrete atoms. 12 In Nominal SOS, languages can instead be defined in a way that a particular atom may affect the computation. and Abella are based on the so-called -tree approach to syntax where a logic that has its roots in the -calculus takes care of the binding management. In Nominal SOS, the management of binders is not delegated to an underlying layer and users need to specify the treatment of binders completely. As another difference, in the mentioned approaches -conversion is built-in and guaranteed on the meta-level. In Nominal SOS -conversion is not built-in but it can be automatically generated from the signature. The user can replace it and experiment with alternative notions at will. Moreover, we prefer to model -equivalence as a transition like any other, so that it can be the subject of meta-theorems based on the shape of rules that may be developed in the future.
We refer the reader to Section 5.8 of [7], where related works are considered in much more detail.
7 Conclusions and Future Work
In this paper, we have introduced a framework, called Nominal SOS, for mod-elling the operational semantics of nominal calculi. The framework comes equipped with the basic features used in defining such calculi, namely, substitution and -conversion. We used the framework to specify the semantics of the early -calculus and lazy -calculus and showed that our formulations of the semantics coincide with the original ones. A notion of nominal bisimilarity arises naturally from our framework. Moreover, we showed that the notion of nominal bisimilarity in our semantics of the early -calculus coincides with open bisimilarity in the original semantics. We also proved that nominal bisimilarity coincides with Abramsky’s applicative bisimilarity in the context of the lazy -calculus.
The main goals of our future work are to provide further evidence that Nominal SOS is expressive enough to capture the original semantics of nominal calculi, such as variants of the -calculus and its higher-order version [27], the psi-calculi [5] and the object calculi [1]. Also, we plan to address different notions of equivalence betweens terms. To begin with, we plan to adapt nominal bisimilarity in order for it to coincide with open bisimilarity with distinctions [29,28], when applied to -calculus terms. Our main goal is however to develop the meta-theory of Nominal SOS. By way of example, it would be worth providing congruence formats for behavioural semantics, possibly generalizing those proposed in [32] and [10], for instance.
References
[1] Martín Abadi and Luca Cardelli. A Theory of Objects. Monographs in Computer Science. Springer-Verlag, New York, 1996.
[2] Samson Abramsky. The lazy lambda calculus. In D.A. Turner, editor, Research Topics in Functional Programming, pages 65–116. Addison Wesley, Reading, Mass., 1990.
[3] Luca Aceto, Wan Fokkink, and Chris Verhoef. Structural operational semantics. In Handbook of Process Algebra, pages 197–292. Elsevier, 1999.
[4] Henk P. Barendregt. The Lambda Calculus: Its Syntax and Semantics, Revised edition. North Holland, 1984.
[5] Jesper Bengtson, Magnus Johansson, Joachim Parrow, and Björn Victor. Psi-calculi: Mobile processes, nominal data, and logic. In Proceedings of the 24th Annual IEEE Symposium on Logic In Computer Science, pages 39–48, Washington, DC, USA, 2009. IEEE Computer Society.
[6] Christiano de O. Braga, Edward H. Haeusler, José Meseguer, and Peter D. Mosses. Mapping modular sos to rewriting logic. In Proceedings of the 12th international conference on Logic based program synthesis and transformation, LOPSTR’02, pages 262–277, Berlin, Heidelberg, 2003. Springer-Verlag.
[7] Matteo Cimini. Contributions to the Meta-Theory of Structural Operational Semantics. Ph.D. in Computer science, School of Computer Science, Reykjavik University, 2012. available at http://cimini.info.
[8] Matteo Cimini, Mohammadreza Mousavi, Michel A. Reniers, and Murdoch J. Gabbay. Nominal SOS - Online Resource. available at: http://cimini.info/publications/publications.html.
[9] Maribel Fernandez and Murdoch J. Gabbay. Nominal rewriting. Information and Computation, 205(6):917–965, 2007.
[10] Marcelo Fiore and Sam Staton. A congruence rule format for name-passing process calculi from mathematical structural operational semantics. In Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science, pages 49–58, Washington, DC, USA, 2006. IEEE Computer Society.
[11] Murdoch J. Gabbay and Andrew 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.
[12] Andrew Gacek, Dale Miller, and Gopalan Nadathur. Reasoning in Abella about structural operational semantics specifications. In A. Abel and C. Urban, editors, International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP 2008), number 228 in Electronic Notes in Theoretical Computer Science, pages 85–100, 2008.
[13] Pieter H. Hartel. Letos - a lightweight execution tool for operational semantics. Software - Practice and Experience, 29:1379–1416, December 1999.
[14] Matthew R. Lakin. An executable meta-language for inductive definitions with binders. PhD thesis, University of Cambridge, 2010.
[15] Matthew R. Lakin and Andrew M. Pitts. A metalanguage for structural operational semantics. In Symposium on Trends in Functional Programming, pages 1–16, 2007.
[16] Dale Miller and Alwen Tiu. A proof theory for generic judgments. ACM Transactions on Computational Logic, 6:749–783, October 2005.
[17] Robin Milner. Communication and Concurrency. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1989.
[18] Robin Milner, Joachim Parrow, and David Walker. A calculus of mobile processes, part i. Information and Computation, 100, 1989.
[19] Robin Milner, Joachim Parrow, and David Walker. A calculus of mobile processes, ii. Information and Computation, 100:41–77, September 1992.
[20] Mohammad Reza Mousavi and Michel A. Reniers. Prototyping sos meta-theory in maude. Electronic Notes in Theoretical Computer Science, 156:135–150, May 2006.
[21] Mohammad Reza Mousavi, Michel A. Reniers, and Jan F. Groote. Sos formats and meta-theory: 20 years after. Theoretical Computer Science, 373(3):238–272, 2007.
[22] David Park. Concurrency and automata on infinite sequences. In Proceedings of the 5th GI-Conference on Theoretical Computer Science, volume 104 of Lecture Notes in Computer Science, pages 167–183, London, UK, 1981. Springer-Verlag.
[23] Andrew M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186:2003, 2002.
[24] Gordon D. Plotkin. A Structural Approach to Operational Semantics. Technical Report DAIMI FN-19, University of Aarhus, 1981.
[25] Gordon D. Plotkin. A structural approach to operational semantics. Journal of Logic and Algebraic Programming, 60-61:17–139, 2004.
[26] Davide Sangiorgi. Bisimulation for higher-order process calculi. Information and Computation, 131(2):141–178, 1996.
[27] Davide Sangiorgi. pi-calculus, internal mobility, and agent-passing calculi. In Selected papers from the 6th international joint conference on Theory and practice of software development, TAPSOFT ’95, pages 235–274, Amsterdam, The Netherlands, The Netherlands, 1996. Elsevier Science Publishers B. V.
[28] Davide Sangiorgi. A theory of bisimulation for the -calculus. Acta Informatica, 33(1):69–97, 1996.
[29] Davide Sangiorgi and David Walker. The -calculus: a Theory of Mobile Processes. Cambridge Univ. Press, 2001.
[30] Bent Thomsen. A theory of higher order communicating systems. Information and Computation, 116(1):38–57, 1995.
[31] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal unification. Theoretical Computer Science, 323:473–497, 2004.
[32] Axelle Ziegler, Dale Miller, and Dale Palamidessi. A congruence format for name-passing calculi. In Proceedings of the 2nd Workshop on Structural Operational Semantics (SOS’05), volume 156 of Electronic Notes in Theoretical Computer Science, pages 169–189, Lisbon, Portugal, 2005. Elsevier Science B.V.
Notes
1 Binding-closed terms corresponds to those that in literature are usually called closed. For instance, in the context of the -calculus the -term () is closed, as it does not contain free variables, see [2,4]. We adopt a different nomenclature in order to avoid confusion with the standard concept of closed term of SOS, i.e., a term that contains no variables. ↩
2 Theorem 4.1 is stated as Theorem 2 in Section 4.1 of [8] and proved in Section 13 of that paper. ↩
3 In the nominal world, the standard definition of -equivalence is based on permutations, see [11] for instance. However, we preferred to model the standard definition of -equivalence. ↩
4 Theorem 4.3 is stated as Theorem 3 in Section 4.2 of [8] and proved in Section 14 of that paper. ↩
5 The encoding can be found in Section 5.2 of [8]. By way of example the reader can consider that ()()0 ([](()( []0))). ↩
6 Theorem 5.1 is stated as Theorem 5 in Section 5.2 of [8] and proved in Section 16 of that paper. ↩
7 Theorem 5.3 is stated as Theorem 7 in Section 6 of [8] and proved in Section 22 of that paper. ↩
8 The premises (#) of rule (abs2AP) ensure that the parameter passing is performed with binding-closed terms only. This characterization already appeared in [9, Section 9.2]. ↩
9 The encoding can be found in Section 5.1 of [8]. By way of example the reader can consider that () ([](([]()))). ↩
10 Theorem 5.4 is stated and proved as Theorem 18 in Section 25 of [8]. ↩
11 Theorem 5.6 is stated as Theorem 13 in Section 7.1 of [8] and proved in Section 25 of that paper. ↩
12 This property is known in the nominal world as the equivariance property, see [11] and especially [23]. ↩