一个移动进程演算的互模拟同余定义框架

并发计算模型是理论计算机科学研究的重要领域之一。以π演算为代表的移动进程演算是目前并发理论的研究热点。互模拟等价定义是移动进程演算研究中的核心概念和问题,而传名机制使得移动进程演算中的互模拟同余关系更加复杂和有趣。本文在分析了常见的互模拟同余定义的基础上,通过抽取定义的核心要素,提出了一个三维的互模拟同余定义模型,从而将一般文献中常见的互模拟定义纳入到一个统一的框架中来,加深了我们对移动进程演算中互模拟概念的理解;同时本文利用这个模型,系统分析了各种互模拟之阿的关系。模型的优点在于它的普适性和开放性。     

Process Calculifor Describing Distributed Systems

ProcessCalculi,suchasCCS~[1]orCSP~[2],weredesignedtodescribeandtoanalysecommunicat-ingsystems.Intuitivelywiththeselanguageasystemisdescribedintermsofasetofindependentprocesseswhichperiodicallysynchronisetheirbehaviourbyhand-shakecommunication.Thissyn-chronisationismodeledasthesimultaneousoccurrenceofanactiontogetherwithitscomplementaryaction,eachbeingperformedbyseparateindependentprocesses.Theseideaswerequicklyextendedtovalue-passingprocesses,wheretheideaofasynchronisationactionismademoreco…     

Contextual Labelled Semantics for Higher-order Process Calculi

In this paper, we study a contextual labelled transition semantics for Higher-Order process calculi. The labelled transition semantics are relatively clean and simple, and corresponding bisimulation equivalence can be easily formulated based on it. Besides we develop a novel approach to reason about behaviours of a higher-order substituted process P{Q/X}, based on which we can directly prove a very important result – factorisation theorem. To show the correspondence between our semantics and the well-established ones, we characterize our bisimulation in a version of barbed equivalence.     

An Abstract Machine for a Higher-Order Distributed Process Calculus

This paper presents the formal specification of an abstract machine or the M-calculus, a new distributed process calculus. The M-calculus can be understood as an extension of the Join calculus that realizes an original combination of the following features: programmable localities, higher-order functions and processes, process mobility, and dynamic binding. Our abstract machine covers these different features and presents a modular structure that clearly separates the sequential (functional) evaluation mechanism from the execution core, and the latter from basic marshalling, location and routing mechanisms.     

Bisimulation for Labelled Markov Processes

In this paper we introduce a new class of labelled transition systems—labelled Markov processes— and define bisimulation for them. Labelled Markov processes are probabilistic labelled transition systems where the state space is not necessarily discrete. We assume that the state space is a certain type of common metric space called an analytic space. We show that our definition of probabilistic bisimulation generalizes the Larsen–Skou definition given for discrete systems. The formalism and mathematics is substantially different from the usual treatment of probabilistic process algebra. The main technical contribution of the paper is a logical characterization of probabilistic bisimulation. This study revealed some unexpected results, even for discrete probabilistic systems.

• Bisimulation can be characterized by a very weak modal logic. The most striking feature is that one has no negation or any kind of negative proposition.

• We do not need any finite branching assumption, yet there is no need of infinitary conjunction.

We also show how to construct the maximal autobisimulation on a system. In the finite state case, this is just a state minimization construction. The proofs that we give are of an entirely different character than the typical proofs of these results. They use quite subtle facts about analytic spaces and appear, at first sight, to be entirely nonconstructive. Yet one can give an algorithm for deciding bisimilarity of finite state systems which constructs a formula that witnesses the failure of bisimulation.     

Bisimulation and cocongruence for probabilistic systems

We introduce a new notion of bisimulation, called event bisimulation on labelled Markov processes (LMPs) and compare it with the, now standard, notion of probabilistic bisimulation, originally due to Larsen and Skou. Event bisimulation uses a sub σ-algebra as the basic carrier of information rather than an equivalence relation. The resulting notion is thus based on measurable subsets rather than on points: hence the name. Event bisimulation applies smoothly for general measure spaces; bisimulation, on the other hand, is known only to work satisfactorily for analytic spaces. We prove the logical characterization theorem for event bisimulation without having to invoke any of the subtle aspects of analytic spaces that feature prominently in the corresponding proof for ordinary bisimulation. These complexities only arise when we show that on analytic spaces the two concepts coincide. We show that the concept of event bisimulation arises naturally from taking the co-congruence point of view for probabilistic systems. We show that the theory can be given a pleasing categorical treatment in line with general coalgebraic principles. As an easy application of these ideas we develop a notion of “almost sure” bisimulation; the theory comes almost “for free” once we modify Giry’s monad appropriately.     

Branching Bisimulation Congruence for Probabilistic Systems

The notion of branching bisimulation for the alternating model of probabilistic systems is not a congruence with respect to parallel composition. In this paper we first define another branching bisimulation in the more general model allowing consecutive probabilistic transitions, and we prove that it is compatible with parallel composition. We then show that our bisimulation is actually the coarsest congruence relation included in the existing branching bisimulation when restricted to the alternating model.     

Open Bisimulation, Revisited

In the context of the π-calculus, open bisimulation is prominent and popular due to its congruence properties and its easy implementability. Motivated by the attempt to generalise it to the spi-calculus, we offer a new, more refined definition and show in how far it coincides with the original one.     

互模拟与逻辑

本文首先讨论了模态逻辑与μ算子的表达能力、博弈语义,给出一阶逻辑与Monadic二阶逻辑的博弈形式,然后讨论互模拟等价在这些逻辑表达能力的核心作用和这些逻辑之间的关系。     

Bisimulation from Open Maps

An abstract definition of bisimulation is presented. It makes possible a uniform definition of bisimulation across a range of different models for parallel computation presented as categories. As examples, transition systems, synchronisation trees, transition systems with independence (an abstraction from Petri nets), and labelled event structures are considered. On transition systems the abstract definition readily specialises to Milner's strong bisimulation. On event structures it explains and leads to a strengthening of the history-preserving bisimulation of Rabinovitch and Traktenbrot and van Glabeek and Goltz. A tie-up with open maps in a (pre)topos, as they appear in the work of Joyal and Moerdijk, brings to light a new model, presheaves on categories of pomsets, into which the usual category of labelled event structures embeds fully and faithfully. As an indication of its promise, this new presheaf model has “refinement” operators. The general approach yields a logic, generalising Hennessy–Milner logic, which is characteristic for the generalised notion of bisimulation.     

Bisimulation and Hidden Algebra

A hidden algebra is a special case of coalgebra. A hidden congruence on a hidden algebra corresponds to a bisimulation equivalence on the corresponding coalgebra. The paper generalizes the notion of hidden congruence to that of hidden bisimulation between two different hidden algebras. We first define hidden bisimulation between two hidden algebras having the same signature. A hidden bisimulation is in fact a bisimulation between the corresponding coalgebras. We then define hidden simulation between two hidden algebras having different signatures related by a vertical signature morphism. We prefer to call this relation simulation because it is unidirectional, due to the signature morphism. For the last case, the relationship between simulation and refinement is discussed.     

Bisimulation is two-way simulation

We give here a simple proof of the fact that on transition systems bisimulation is the equivalence relation generated by simulation via functions. The proof entirely rests on simple rules of the calculus of relations.     

Calculi for interaction

Action structures have previously been proposed as an algebra for both the syntax and the semantics of interactive computation. Here, a class of concrete action structures calledaction calculi is identified, which can serve as a non-linear syntax for a wide variety of models of interactive behaviour. Each action in an action calculus is represented as an assembly ofmolecules; the syntactic binding ofnames is the means by which molecules are bound together. A graphical form,action graphs, is used to aid presentation. One action calculus differs from another only in its generators, calledcontrols. Action calculi generalise a previously defined action structure PIC for the π- calculus. Several extensions to PIC are given as action calculi, giving essentially the same power as the π-calculus. An action calculus is also given for the typed λ-calculus, and for Petri nets parametrized on their places and transitions. An equational characterization of action calculi is given: each action calculusA is the quotient of a term algebra by certain equations. The terms are generated by a set of operators, including those basic to all action structures as well as the controls specific toA; the equations are the basic axioms of action structures together with four additional axiom schemata.     

Calculi for interaction

Action structures have previously been proposed as an algebra for both the syntax and the semantics of interactive computation. Here, a class of concrete action structures called action calculi is identified, which can serve as a non-linear syntax for a wide variety of models of interactive behaviour. Each action in an action calculus is represented as an assembly of molecules; the syntactic binding of names is the means by which molecules are bound together. A graphical form, action graphs, is used to aid presentation. One action calculus differs from another only in its generators, called controls. Action calculi generalise a previously defined action structure for the -calculus. Several extensions to are given as action calculi, giving essentially the same power as the -calculus. An action calculus is also given for the typed -calculus, and for Petri nets parametrized on their places and transitions. An equational characterization of action calculi is given: each action calculus is the quotient of a term algebra by certain equations. The terms are generated by a set of operators, including those basic to all action structures as well as the controls specific to ; the equations are the basic axioms of action structures together with four additional axiom schemata. Received May 12, 1995 / August 7, 1995     

Notes on Generative Probabilistic Bisimulation

In this notes we consider the model of Generative Probabilistic Transition Systems, and Baier and Hermanns' notion of weak bisimulation defined over them. We prove that, if we consider any process algebra giving rise to a Probabilistic Transition System satisfying the condition of regularity and offering prefixing, interleaving, and guarded recursion, then the coarsest congruence that is contained in weak bisimulation is strong bisimulation.     

Process Calculi à la Bird-Meertens

This paper is an attempt to apply the reasoning principles and calculational style underlying the so-called Bird-Meertens formalism to the design of process calculi, parametrized by a behaviour model. In particular, basically equational and pointfree proofs of process properties are given, relying on the universal characterisation of anamorphisms and therefore avoiding the explicit construction of bisimulations. The developed calculi can be directly implemented on a functional language supporting coinductive types, which provides a convenient way to prototype processes and assess alternative design decisions.     

Bisimulation equivalence of differential-algebraic systems

In this paper, the notion of bisimulation relation for linear input-state-output systems is extended to general linear differential-algebraic (DAE) systems. Geometric control theory is used to derive a linear-algebraic characterisation of bisimulation relations, and an algorithm for computing the maximal bisimulation relation between two linear DAE systems. The general definition is specialised to the case where the matrix pencil sE ? A is regular. Furthermore, by developing a one-sided version of bisimulation, characterisations of simulation and abstraction are obtained.     

Higher-Order Nets for Mobile Policies

Since the early 80's the combination of Petri nets and rule-based transformations has been extensively researched to obtain new concepts and results. In this paper we consider rules as tokens leading to the concept of higher-order nets for mobile policies. The rules are used on the one hand for the specification of policy rules and on the other hand for the modification of policy rules, i.e. for the definition of new rules by reusing existing rules. So the higher-order net models distribution and modification of policy rules in a systematic and structured way. We give HasCasl-specifications of rules and (local) transformations in the sense of the double-pushout approach and illustrate our concept by a small system inspired by the case study of a tax refund process [E. Bertino, E. Ferrari, E., and V. Atluri. The Specification and Enforcement of Authorization Constraints in Workflow Management Systems. ACM Transactions on Information and System Security 2 (1) (1999) 65–104].     

Monotonicity Inference for Higher-Order Formulas

Formulas are often monotonic in the sense that satisfiability for a given domain of discourse entails satisfiability for all larger domains. Monotonicity is undecidable in general, but we devised three calculi that infer it in many cases for higher-order logic. The third calculus has been implemented in Isabelle’s model finder Nitpick, where it is used both to prune the search space and to soundly interpret infinite types with finite sets, leading to dramatic speed and precision improvements.