Using Baire metric, this paper proposes a generalized framework of transition system approximation by developing the notions of approximate reachability and approximate bisimulation equivalences. The proposed framewor...Using Baire metric, this paper proposes a generalized framework of transition system approximation by developing the notions of approximate reachability and approximate bisimulation equivalences. The proposed framework captures the traditional exact equivalence as a special case. Approximate reachability equivalence is coarser than approximate bisimulation equivalence, just like the hierarchy of the exact ones. Both approximate equivalences satisfy the transitive property, consequently, they can be used in transition system approximation.展开更多
An algorithm for the verification of strong open bisimulation in π-calculus with mismatch was presented, which is based on the symbolic transition graph (STG). Given two processes, we can convert them into two STGs b...An algorithm for the verification of strong open bisimulation in π-calculus with mismatch was presented, which is based on the symbolic transition graph (STG). Given two processes, we can convert them into two STGs by a set of rules at first. Next, the algorithm computes a predicate equation system (PES) from the STGs. This is the key step of the whole algorithm. Finally, the PES is solved and the greatest symbolic solution is got. Correctness of the algorithm is proved and time complexity discussed. It is shown that the worst-case time complexity is exponential.展开更多
This paper carries out a systematic investigation into the bisimulation lattice of asymmetric chi calculus with a mismatch combinator. It is shown that all the sixty three L bisimilarities collapse to twelve distinct ...This paper carries out a systematic investigation into the bisimulation lattice of asymmetric chi calculus with a mismatch combinator. It is shown that all the sixty three L bisimilarities collapse to twelve distinct relations and they form a bisimulation lattice with respect to set inclusion. The top of the lattice coincides with the barbed bisimilarity.展开更多
Information networks are becoming increasingly important in practice. However, their escalating complexity is gradually impeding the efficiency of data mining. A novel network schema called the Behavior Schema of Info...Information networks are becoming increasingly important in practice. However, their escalating complexity is gradually impeding the efficiency of data mining. A novel network schema called the Behavior Schema of Information Networks (BSIN) is proposed to address this issue. This work defines the behavior of nodes as connected paths in BSIN, proposes a novel function distinguish behavior differences, and introduces approximate bisimulation into the acquisition of quotient sets for node types. The major highlight of BSIN is its ability to directly obtain a high-efficiency network on the basis of approximate bisimulation, rather than reducing the existing information network. It provides an effective representation of information networks, and the resulting novel network has a simple structure that more efficiently expresses semantic information than current network representations. The theoretical analysis of the connected paths between the original and the obtained networks demonstrates that errors are controllable;and semantic information is approximately retained. Case studies show that BSIN yields a simple network and is highly cost-effective.展开更多
In this paper, a labelled transition semantics for higher-order processcalculi is studied. The labelled transition semantics is relatively clean and simple, andcorresponding bisimulation equivalence can be easily form...In this paper, a labelled transition semantics for higher-order processcalculi is studied. The labelled transition semantics is relatively clean and simple, andcorresponding bisimulation equivalence can be easily formulated based on it. And the congruenceproperties of the bisimulation equivalence can be proved easily. To show the correspondence betweenthe proposed semantics and the well-established ones, the bisimulation is characterized as a versionof barbed equivalence and a version of context bisimulation.展开更多
Symbolic transition graph is proposed as an intuitive and compact semantic model for the π-calculus processes.Various versions (strong/weak, ground/symbolic) of early operational semantics are given to such graphs. B...Symbolic transition graph is proposed as an intuitive and compact semantic model for the π-calculus processes.Various versions (strong/weak, ground/symbolic) of early operational semantics are given to such graphs. Based on them the corresponding versions of early bisimulation equivalences and observation congruence are defined. The notions of symbolic observation graph and symbolic congruence graph are also introduced, and followed by two theorems ensuring the elimination of τ-cycles and τ-edges. Finally algorithms for checking strong/weak early bisimulation equivalences and observation congruence are presented together with their correctness proofs. These results fuse and generalize the strong bisimulation checking algorithm for value-passing processes and the verification technique for weak bisimulation of pure-CCS to the finite control π-calculus.展开更多
Symbolic bisimulation avoids the infinite branching problem causedby instantiating input names with all names in the standard definition of bisimulation in л-calculus. However, it does not automatically lead to an ef...Symbolic bisimulation avoids the infinite branching problem causedby instantiating input names with all names in the standard definition of bisimulation in л-calculus. However, it does not automatically lead to an efficient algorithm,because symbolic bisimulation is indexed by conditions on names,and directly manipulating such conditions can be computationally costly. In this paper a new notionof bisimulation is introduced, in which the manipulation of maximally consistent conditions is replaced with a systematic employment of schematic names. It is shownthat the new notion captures symbolic bisimulation in a precise sense. Based on thenew definition an efficient algorithm, which instantiates input names 'on-the-fly', ispresented to check bisimulations for finite-control л-calculus.展开更多
This study is concerned with probabilistic Boolean control networks(PBCNs)with state feedback control.A novel definition of bisimilar PBCNs is proposed to lower computational complexity.To understand more on bisimulat...This study is concerned with probabilistic Boolean control networks(PBCNs)with state feedback control.A novel definition of bisimilar PBCNs is proposed to lower computational complexity.To understand more on bisimulation relations between PBCNs,we resort to a powerful matrix manipulation called semi-tensor product(STP).Because stabilization of networks is of critical importance,the propagation of stabilization with probability one between bisimilar PBCNs is then considered and proved to be attainable.Additionally,the transient periods(the maximum number of steps to implement stabilization)of two PBCNs are certified to be identical if these two networks are paired with a bisimulation relation.The results are then extended to the probabilistic Boolean networks.展开更多
Deciding bisimulation equivalence of two normed pushdown automata is one of the most fundamental problems in formal verification.The problem is proven to be ACKER-MANN-complete recently.Both the upper bound and the lo...Deciding bisimulation equivalence of two normed pushdown automata is one of the most fundamental problems in formal verification.The problem is proven to be ACKER-MANN-complete recently.Both the upper bound and the lower bound results indicate that the number of control states is an important parameter.In this paper,we study the parametric complexity of this problem.We refine previous results in two aspects.First,we prove that the bisimulation equivalence of normed PDA with two states is EXPTIME-hard.Second,we prove that the bisimulation equivalence of normed PDA with d states is in F_(d+3),which improves the best known upper bound F_(d+4) of this problem.展开更多
The ehi calculus is a model of mobile processes. It has evolved from the pi-calculus with motivations from simplification aml communication-as-cut-eliminatinn. This paper studies the ehi calculus in the framework inco...The ehi calculus is a model of mobile processes. It has evolved from the pi-calculus with motivations from simplification aml communication-as-cut-eliminatinn. This paper studies the ehi calculus in the framework incorporating asymmetric communication. The major feature of the calculus is the identification of two actions： x/x and τ. The investigalion on the barbed bisimilarity shows how the property affects the observational theory. Based on the definition of the barbed bisimilarity, the simulation properties of the barbed bisimilarity are studied. It shows that the algebraic properties of the barbed bisimiilarity have changed greatly compared with the chi calculus.Although the definition of the barbed bisimilarity is very simple, the properly of closeness under contexts makes it difficuh to understand the barbed bisimilarity directly. Therefore an open style definition of the barbed bisimilarity is given, which is a context free description of barbed bisimilarity. Its definition is complex, but it is a well-behaved relation for it coincides with the barbed bisimilarity. It also helps to build an axiomatization system for the bathed congruence. Besides the axioms for the strong barbed bisimilarity, the paper proposes a new tau law and four new update laws for the barbed congruence. Both the operational and algebraic properties of the enriched calculus improve the understanding of the bisimulation behaviors of the model.展开更多
A reasonable transition rule is proposed for synchronized actions and someequational properties of bisimilarity and weak bisimilarity in the process algebra for reasoningabout concurrent actions are presented.
An alternative presentation of the π-calculus is given. This version of the π-calculus is symmetric in the sense that communications are symmetric and there is no dtherence between input and output prehxes. The poin...An alternative presentation of the π-calculus is given. This version of the π-calculus is symmetric in the sense that communications are symmetric and there is no dtherence between input and output prehxes. The point of the symmetric π-calculus is that it has no abstract names. The set of closed names is therefore homogeneous. The π-calculus can be fully embedded into the symmtric π-calculus. The symmetry changes the emphasis of the communication mechanism of the π-calculus and opens up possibility for further variations.展开更多
We propose a fully abstract semantics for valuepassing CCS for trees (VCCTS) with the feature that processes are located at the vertices of a graph whose edges describe possible interaction capabilities. The operation...We propose a fully abstract semantics for valuepassing CCS for trees (VCCTS) with the feature that processes are located at the vertices of a graph whose edges describe possible interaction capabilities. The operational semantics is given both in terms of a reduction semantics and in terms of a labelled transition semantics. We develop a theory of behavioral equivalences by introducing both weak barbed congruence and weak bisimilarity. In particular, we show that, on image-finite processes, weak barbed congruence coincides with weak bisimilarity. To illustrate potential applications and the powerful expressiveness of VCCTS, we formally compare VCCTS with some well-known models, e.g., dynamic pushdown networks, top-down tree automata and value-passing CCS.展开更多
In the study of process calculi, encoding between different calculi is an effective way to compare the expressive power of calculi and can shed light on the essence of where the difference lies. Thomsen and Sangiorgi ...In the study of process calculi, encoding between different calculi is an effective way to compare the expressive power of calculi and can shed light on the essence of where the difference lies. Thomsen and Sangiorgi have worked on the higher-order calculi （higher-order Calculus of Communicating Systems （CCS） and higher-order π-calculus, respectively） and the encoding from and to first-order π-calculus. However a fully abstract encoding of first-order π-calculus with higher-order CCS is not available up-today. This is what we intend to settle in this paper. We follow the encoding strategy, first proposed by Thomsen, of translating first-order π-calculus into Plain CHOCS. We show that the encoding strategy is fully abstract with respect to early bisimilarity （first-order π-calculus） and wired bisimilarity （Plain CHOCS） （which is a bisimulation defined on wired processes only sending and receiving wires）, that is the core of the encoding strategy. Moreover from the fact that the wired bisimilarity is contained by the well-established context bisimilarity, we secure the soundness of the encoding, with respect to early bisimilarity and context bisimilarity. We use index technique to get around all the technical details to reach these main results of this paper. Finally, we make some discussion on our work and suggest some future work.展开更多
Correctness is a key attribute of software. Parameterized bisimulation provides a kind of abstract description to verify the correctness of software under environment. In real world situations, many softwares contain ...Correctness is a key attribute of software. Parameterized bisimulation provides a kind of abstract description to verify the correctness of software under environment. In real world situations, many softwares contain some probabilistic information. In this paper, we focus on the probabilistic construction of parameterized bisimulation. Firstly, we extend parameterized bisimulation to probabilistic parameterized bisimulation. Secondly, a quantitative model of approximate correctness of software is proposed. Finally, the subsititutivity laws of quantitative model with various combinators are proved.展开更多
Modal logic characterization in a higher-order setting is usually not a trivial task because higher-order process-passing is quite different from first-order name-passing. We study the logical characterization of high...Modal logic characterization in a higher-order setting is usually not a trivial task because higher-order process-passing is quite different from first-order name-passing. We study the logical characterization of higherorder processes constrained by linearity. Linearity respects resource-sensitiveness and does not allow processes to duplicate themselves arbitrarily. We provide a modal logic that characterizes linear higher-order processes,particularly the bisimulation called local bisimulation over them. More importantly, the logic has modalities for higher-order actions downscaled to resembling first-order ones in Hennessy-Milner logic, based on a formulation exploiting the linearity of processes.展开更多
The X calculus is a model of concurrent and mobile systems. It emphasizes that communications are information exchanges. In the paper, two constructions are incorporated into the framework of the chi calculus, which a...The X calculus is a model of concurrent and mobile systems. It emphasizes that communications are information exchanges. In the paper, two constructions are incorporated into the framework of the chi calculus, which are asymmetric communication and mismatch condition widely used in applications. Since the barbed bisimilarity has proved its generality and gained its popularity as an effective approach to generating a reasonable observational equivalence, we study both the operational and algebraic properties of the barbed bisimilarity in this enriched calculus. The investigation supports an improved understanding of the bisimulation behaviors of the model. It also gives a general picture of how the two constructions affect the observational theory.展开更多
In the context of process calculi, higher order π calculus （A calculus） is prominent and popular due to its ability to transfer processes. Motivated by the attempt to study the process theory in an integrated way, ...In the context of process calculi, higher order π calculus （A calculus） is prominent and popular due to its ability to transfer processes. Motivated by the attempt to study the process theory in an integrated way, we give a system study of A calculus with respect to the model independent framework. We show the coincidence of the context bisimulation to the absolute equality. We also build a subbisimilarity relation from A calculus to the π calculus.展开更多
This paper focuses on the problem of seeking complete axiomatization for finite processes in the process calculus called symbolic probabilistic π-calculus introduced by Wu,Palamidessi and Lin.We provide inference sys...This paper focuses on the problem of seeking complete axiomatization for finite processes in the process calculus called symbolic probabilistic π-calculus introduced by Wu,Palamidessi and Lin.We provide inference systems for both strong and weak symbolic probabilistic bisimulations and also prove their soundness and completeness.This is the first work,to our knowledge,that provides complete axiomatization for symbolic probabilistic bisimulations in the presence of both nondeterministic and probabilistic choice.展开更多
A polynomial algorithm for the regularity problem of weak and branching bisimilarity on totally normed process algebra(PA) processes is given. Its time complexity is O(n3+ mn), where n is the number of transition rule...A polynomial algorithm for the regularity problem of weak and branching bisimilarity on totally normed process algebra(PA) processes is given. Its time complexity is O(n3+ mn), where n is the number of transition rules and m is the maximal length of the rules. The algorithm works for totally normed basic process algebra(BPA) as well as basic parallel process(BPP).展开更多
基金Supported by the National Natural Science Foundation of China(No.11371003 and No.11461006)the Natural Science Foundation of Guangxi(No.2011GXNSFA018154 and No.2012GXNSFGA060003)
文摘Using Baire metric, this paper proposes a generalized framework of transition system approximation by developing the notions of approximate reachability and approximate bisimulation equivalences. The proposed framework captures the traditional exact equivalence as a special case. Approximate reachability equivalence is coarser than approximate bisimulation equivalence, just like the hierarchy of the exact ones. Both approximate equivalences satisfy the transitive property, consequently, they can be used in transition system approximation.
基金National Natural Science Foundation of China ( No. 6 98730 32 ) 86 3Hi-Τ ech Project ( 86 3-30 6 -ZT-0 6 -0 2 -2 )
文摘An algorithm for the verification of strong open bisimulation in π-calculus with mismatch was presented, which is based on the symbolic transition graph (STG). Given two processes, we can convert them into two STGs by a set of rules at first. Next, the algorithm computes a predicate equation system (PES) from the STGs. This is the key step of the whole algorithm. Finally, the PES is solved and the greatest symbolic solution is got. Correctness of the algorithm is proved and time complexity discussed. It is shown that the worst-case time complexity is exponential.
文摘This paper carries out a systematic investigation into the bisimulation lattice of asymmetric chi calculus with a mismatch combinator. It is shown that all the sixty three L bisimilarities collapse to twelve distinct relations and they form a bisimulation lattice with respect to set inclusion. The top of the lattice coincides with the barbed bisimilarity.
基金supported by the National Natural Science Foundation of China(No.12261027)the Innovation Project of Guangxi Graduate Education(No.YCBZ2021027).
文摘Information networks are becoming increasingly important in practice. However, their escalating complexity is gradually impeding the efficiency of data mining. A novel network schema called the Behavior Schema of Information Networks (BSIN) is proposed to address this issue. This work defines the behavior of nodes as connected paths in BSIN, proposes a novel function distinguish behavior differences, and introduces approximate bisimulation into the acquisition of quotient sets for node types. The major highlight of BSIN is its ability to directly obtain a high-efficiency network on the basis of approximate bisimulation, rather than reducing the existing information network. It provides an effective representation of information networks, and the resulting novel network has a simple structure that more efficiently expresses semantic information than current network representations. The theoretical analysis of the connected paths between the original and the obtained networks demonstrates that errors are controllable;and semantic information is approximately retained. Case studies show that BSIN yields a simple network and is highly cost-effective.
文摘In this paper, a labelled transition semantics for higher-order processcalculi is studied. The labelled transition semantics is relatively clean and simple, andcorresponding bisimulation equivalence can be easily formulated based on it. And the congruenceproperties of the bisimulation equivalence can be proved easily. To show the correspondence betweenthe proposed semantics and the well-established ones, the bisimulation is characterized as a versionof barbed equivalence and a version of context bisimulation.
基金Project partially supported by the 863 Hi-Tech Project (Grant No. 863-306-ZT05-06-1)the National Natural Science Foundation of China (Grant No. 69873045).
文摘Symbolic transition graph is proposed as an intuitive and compact semantic model for the π-calculus processes.Various versions (strong/weak, ground/symbolic) of early operational semantics are given to such graphs. Based on them the corresponding versions of early bisimulation equivalences and observation congruence are defined. The notions of symbolic observation graph and symbolic congruence graph are also introduced, and followed by two theorems ensuring the elimination of τ-cycles and τ-edges. Finally algorithms for checking strong/weak early bisimulation equivalences and observation congruence are presented together with their correctness proofs. These results fuse and generalize the strong bisimulation checking algorithm for value-passing processes and the verification technique for weak bisimulation of pure-CCS to the finite control π-calculus.
文摘Symbolic bisimulation avoids the infinite branching problem causedby instantiating input names with all names in the standard definition of bisimulation in л-calculus. However, it does not automatically lead to an efficient algorithm,because symbolic bisimulation is indexed by conditions on names,and directly manipulating such conditions can be computationally costly. In this paper a new notionof bisimulation is introduced, in which the manipulation of maximally consistent conditions is replaced with a systematic employment of schematic names. It is shownthat the new notion captures symbolic bisimulation in a precise sense. Based on thenew definition an efficient algorithm, which instantiates input names 'on-the-fly', ispresented to check bisimulations for finite-control л-calculus.
基金Project supported by the National Natural Science Foundation of China(Nos.61603268 and 61773319)the Fundamental Research Funds for the Central Universities,China(No.JBK190502)。
文摘This study is concerned with probabilistic Boolean control networks(PBCNs)with state feedback control.A novel definition of bisimilar PBCNs is proposed to lower computational complexity.To understand more on bisimulation relations between PBCNs,we resort to a powerful matrix manipulation called semi-tensor product(STP).Because stabilization of networks is of critical importance,the propagation of stabilization with probability one between bisimilar PBCNs is then considered and proved to be attainable.Additionally,the transient periods(the maximum number of steps to implement stabilization)of two PBCNs are certified to be identical if these two networks are paired with a bisimulation relation.The results are then extended to the probabilistic Boolean networks.
基金supported by the National Natural Foundation of China(Grant Nos.62072299,61872142,61772336,61572318)the Open Project of Shanghai Key Laboratory of Trustworthy Computing(OP202102)。
文摘Deciding bisimulation equivalence of two normed pushdown automata is one of the most fundamental problems in formal verification.The problem is proven to be ACKER-MANN-complete recently.Both the upper bound and the lower bound results indicate that the number of control states is an important parameter.In this paper,we study the parametric complexity of this problem.We refine previous results in two aspects.First,we prove that the bisimulation equivalence of normed PDA with two states is EXPTIME-hard.Second,we prove that the bisimulation equivalence of normed PDA with d states is in F_(d+3),which improves the best known upper bound F_(d+4) of this problem.
基金Sponsored by the National Distinguished Young Scientist Fund of NNSFC(Grant No.60225012)the National 973 Project(Grant No.2003CB316905)BDCC(Grant No.03DZ14025).
文摘The ehi calculus is a model of mobile processes. It has evolved from the pi-calculus with motivations from simplification aml communication-as-cut-eliminatinn. This paper studies the ehi calculus in the framework incorporating asymmetric communication. The major feature of the calculus is the identification of two actions： x/x and τ. The investigalion on the barbed bisimilarity shows how the property affects the observational theory. Based on the definition of the barbed bisimilarity, the simulation properties of the barbed bisimilarity are studied. It shows that the algebraic properties of the barbed bisimiilarity have changed greatly compared with the chi calculus.Although the definition of the barbed bisimilarity is very simple, the properly of closeness under contexts makes it difficuh to understand the barbed bisimilarity directly. Therefore an open style definition of the barbed bisimilarity is given, which is a context free description of barbed bisimilarity. Its definition is complex, but it is a well-behaved relation for it coincides with the barbed bisimilarity. It also helps to build an axiomatization system for the bathed congruence. Besides the axioms for the strong barbed bisimilarity, the paper proposes a new tau law and four new update laws for the barbed congruence. Both the operational and algebraic properties of the enriched calculus improve the understanding of the bisimulation behaviors of the model.
文摘A reasonable transition rule is proposed for synchronized actions and someequational properties of bisimilarity and weak bisimilarity in the process algebra for reasoningabout concurrent actions are presented.
文摘An alternative presentation of the π-calculus is given. This version of the π-calculus is symmetric in the sense that communications are symmetric and there is no dtherence between input and output prehxes. The point of the symmetric π-calculus is that it has no abstract names. The set of closed names is therefore homogeneous. The π-calculus can be fully embedded into the symmtric π-calculus. The symmetry changes the emphasis of the communication mechanism of the π-calculus and opens up possibility for further variations.
文摘We propose a fully abstract semantics for valuepassing CCS for trees (VCCTS) with the feature that processes are located at the vertices of a graph whose edges describe possible interaction capabilities. The operational semantics is given both in terms of a reduction semantics and in terms of a labelled transition semantics. We develop a theory of behavioral equivalences by introducing both weak barbed congruence and weak bisimilarity. In particular, we show that, on image-finite processes, weak barbed congruence coincides with weak bisimilarity. To illustrate potential applications and the powerful expressiveness of VCCTS, we formally compare VCCTS with some well-known models, e.g., dynamic pushdown networks, top-down tree automata and value-passing CCS.
基金supported by the National Basic Research 973 Program of China under Grant No.2003CB317005the National Natural Science Foundation of China under Grant Nos.60473006 and 60573002the National Research Foundation for the Doctoral Program of Higher Education of China Research Fund under Grant No.20010248033.
文摘In the study of process calculi, encoding between different calculi is an effective way to compare the expressive power of calculi and can shed light on the essence of where the difference lies. Thomsen and Sangiorgi have worked on the higher-order calculi （higher-order Calculus of Communicating Systems （CCS） and higher-order π-calculus, respectively） and the encoding from and to first-order π-calculus. However a fully abstract encoding of first-order π-calculus with higher-order CCS is not available up-today. This is what we intend to settle in this paper. We follow the encoding strategy, first proposed by Thomsen, of translating first-order π-calculus into Plain CHOCS. We show that the encoding strategy is fully abstract with respect to early bisimilarity （first-order π-calculus） and wired bisimilarity （Plain CHOCS） （which is a bisimulation defined on wired processes only sending and receiving wires）, that is the core of the encoding strategy. Moreover from the fact that the wired bisimilarity is contained by the well-established context bisimilarity, we secure the soundness of the encoding, with respect to early bisimilarity and context bisimilarity. We use index technique to get around all the technical details to reach these main results of this paper. Finally, we make some discussion on our work and suggest some future work.
基金Supported by the National Natural Science Foundation of China(61300048)the Anhui Provincial Natural Science Foundation(1308085QF117,1508085MA14)+2 种基金the Key Natural Science Foundation of Universities of Anhui Province(KJ2014A003,KJ2014A223)the Major Teaching Reform Project of Anhui Higher Education Revitalization Plan(2014ZDJY058)the Excellent Young Talents in Universities of Anhui Province
文摘Correctness is a key attribute of software. Parameterized bisimulation provides a kind of abstract description to verify the correctness of software under environment. In real world situations, many softwares contain some probabilistic information. In this paper, we focus on the probabilistic construction of parameterized bisimulation. Firstly, we extend parameterized bisimulation to probabilistic parameterized bisimulation. Secondly, a quantitative model of approximate correctness of software is proposed. Finally, the subsititutivity laws of quantitative model with various combinators are proved.
基金the National Natural Science Foundation of China(Nos.61202023,61261130589 and61173048)the PACE Project(No.12IS02001)the Specialized Research Fund for the Doctoral Program of Higher Edueation of China(No.20120073120031)
文摘Modal logic characterization in a higher-order setting is usually not a trivial task because higher-order process-passing is quite different from first-order name-passing. We study the logical characterization of higherorder processes constrained by linearity. Linearity respects resource-sensitiveness and does not allow processes to duplicate themselves arbitrarily. We provide a modal logic that characterizes linear higher-order processes,particularly the bisimulation called local bisimulation over them. More importantly, the logic has modalities for higher-order actions downscaled to resembling first-order ones in Hennessy-Milner logic, based on a formulation exploiting the linearity of processes.
基金Supported by the National Grand Fundamental Research 973 Program of China under Grant No.2003CB317005the National Natural Science Foundation of China under Grant No.60473006the National Research Foundation for the Doctoral Program of Education of China under Grant No.20010248033.
文摘The X calculus is a model of concurrent and mobile systems. It emphasizes that communications are information exchanges. In the paper, two constructions are incorporated into the framework of the chi calculus, which are asymmetric communication and mismatch condition widely used in applications. Since the barbed bisimilarity has proved its generality and gained its popularity as an effective approach to generating a reasonable observational equivalence, we study both the operational and algebraic properties of the barbed bisimilarity in this enriched calculus. The investigation supports an improved understanding of the bisimulation behaviors of the model. It also gives a general picture of how the two constructions affect the observational theory.
基金the National Natural Science Foundation of China(Nos.61033002,60903020,61202023)the Science and Technology Commission of Shanghai Municipality(No.11XD1402800)
文摘In the context of process calculi, higher order π calculus （A calculus） is prominent and popular due to its ability to transfer processes. Motivated by the attempt to study the process theory in an integrated way, we give a system study of A calculus with respect to the model independent framework. We show the coincidence of the context bisimulation to the absolute equality. We also build a subbisimilarity relation from A calculus to the π calculus.
基金the National Basic Research Program (973) of China (No.2003CB317005)the National Nature Science Foundation of China (Nos.60573002 and 60703033)
文摘This paper focuses on the problem of seeking complete axiomatization for finite processes in the process calculus called symbolic probabilistic π-calculus introduced by Wu,Palamidessi and Lin.We provide inference systems for both strong and weak symbolic probabilistic bisimulations and also prove their soundness and completeness.This is the first work,to our knowledge,that provides complete axiomatization for symbolic probabilistic bisimulations in the presence of both nondeterministic and probabilistic choice.
基金the National Natural Science Foundation of China(Nos.61261130589 and 61033002)the Fund of the Science and Technology Commission of Shanghai Municipality(No.11XD1402800)
文摘A polynomial algorithm for the regularity problem of weak and branching bisimilarity on totally normed process algebra(PA) processes is given. Its time complexity is O(n3+ mn), where n is the number of transition rules and m is the maximal length of the rules. The algorithm works for totally normed basic process algebra(BPA) as well as basic parallel process(BPP).
