Finitary logics for some CCS observational bisimulations

DOI10.1016/0020-0190(92)90141-HMaRDI QIDQ1198052zbMATH OpenOpenAlexFDO

Authors Miranda Mowbray

Publication date 16 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90141-h

zbMATH Keywords

CCSconcurrencesfinitary modal logicformal semanticsobservational bisimulations

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Semantics in the theory of computing (68Q55)

Review text

This paper proves that observational bisimulations for CCS which satisfy certain conditions have a finitary associated modal logic. The conditions involve information on the amount of top-level parallelism of states. This result may add fuel to the interleaving-versus-true-concurrency debate, since it suggests that the ability to observe internal structure of states (which is what distinguishes noninterleaving semantics from interleaving semantics) can lead not only to semantics which are more expressive, but also to semantics which are in some way simpler - their associated modal logics are finitary. Some cases of the result (for instance, Strong Equivalence [\textit{R. Milner}, Communication and concurrency, Prentice Hall, New York (1989; Zbl 0683.68008)] and Pomset Bisimulation Equivalence [\textit{G. Boudal} and \textit{I. Castellani}, Theor. Comput. Sci. 59, No. 1/2, 25-84 (1988; Zbl 0678.68078)] were already known, due to Lemma 1, which was proved in [\textit{M. Hennessy} and \textit{R. Milner}, J. Assoc. Comput. Mach. 32, 137-161 (1985; Zbl 0629.68021)] and is generalized here.

Recommendations

• scientific article; zbMATH DE number 4210118
• Compositionality and bisimulation: A negative result
• Three logics for branching bisimulation
• Publication:4733387
• A modal characterization of observational congruence on finite terms of CCS

Cites work

• A calculus of communicating systems
• Algebraic laws for nondeterminism and concurrency
• Concurrency and atomicity
• scientific article; zbMATH DE number 1638650 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)

Cited in

(3)

• Compositionality and bisimulation: A negative result
• scientific article; zbMATH DE number 4210118 (Why is no real title available?)
• A modal characterization of observational congruence on finite terms of CCS

This page was built for publication: Finitary logics for some CCS observational bisimulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198052)