Journal article
On fixpoint logics and equivalences for processes with restricted nondeterminism
- Abstract:
- In concurrency, processes can be studied using a partial order or an interleaving semantics. In partial order semantics, at least four different kinds of behaviour can be recognized: concurrency, causality, conflict and confusion. In interleaving semantics, only conflicts can be observed. All these features can be characterized in logical terms, and various logics have been defined for this purpose. For instance, Hennessy–Milner logic is a modal language that captures strong bisimilarity, the standard bisimulation equivalence for processes with interleaving semantics. However, when considering processes with partial order semantics, stronger equivalences are used and more discriminating logics are needed. In the present article, we study conditions to ease the definition of such logics and equivalences for processes with partial order semantics. More specifically, we study the impact that nondeterminism can have on some fixpoint modal logics and bisimulation equivalences for concurrent and multi-agent systems, when it is systematically restricted within the four kinds of behaviours mentioned above. Our results show that when the concurrency and confusion relations are taken to be deterministic, then the main equivalence for causal behaviour can be completely captured (even in logical and game-theoretic terms) by a simpler, weaker, more local bisimulation relation. We also provide key examples of the kinds of processes that can be modelled using deterministic confusion to illustrate the expressive power of the general framework defined here.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 351.7KB, Terms of use)
-
- Publisher copy:
- 10.1093/logcom/exv032
Authors
- Publisher:
- Oxford University Press
- Journal:
- Journal of Logic and Computation More from this journal
- Volume:
- 28
- Issue:
- 4
- Pages:
- 779–807
- Publication date:
- 2015-06-08
- DOI:
- EISSN:
-
1465-363X
- ISSN:
-
0955-792X
- Language:
-
English
- Keywords:
- UUID:
-
uuid:375e1c0a-1021-407b-b9c5-96a0a1d42c23
- Deposit date:
-
2015-11-06
- ARK identifier:
Terms of use
- Copyright holder:
- Julian Gutierrez
- Copyright date:
- 2015
- Rights statement:
- © The Author, 2015. Published by Oxford University Press.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Oxford University Press at https://doi.org/10.1093/logcom/exv032
If you are the owner of this record, you can report an update to it here: Report update to this record