Logics and bisimulation games for concurrency, causality and conflict

Conference item

Based on a simple axiomatization of concurrent behaviour we define two ways of observing parallel computations and show that in each case they are dual to conflict and causality, respectively. We give a logical characterization to those dualities and show that natural fixpoint modal logics can be extracted from such a characterization. We also study the equivalences induced by such logics and prove that they are decidable and can be related with well-known bisimulations for interleaving and noninterleaving concurrency. Moreover, by giving a game-theoretical characterization to the equivalence induced by the main logic, which is called Separation Fixpoint Logic (SFL), we show that the equivalence SFL induces is strictly stronger than a history-preserving bisimulation (hpb) and strictly weaker than a hereditary history-preserving bisimulation (hhpb). Our study considers branching-time models of concurrency based on transition systems and petri net structures.

Authors: Gutierrez, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer Berlin Heidelberg
• Host title: Foundations of Software Science and Computational Structures. FoSSaCS 2009
• Pages: 48-62
• Series: Lecture Notes in Computer Science
• Series number: 5504
• Publication date: 2009-03-27
• Event title: 12th International Conference of Foundations of Software Science and Computational Structures (FOSSACS 2009)
• Event location: York, UK
• Event start date: 2009-03-22
• Event end date: 2009-03-29
• DOI: 10.1007/978-3-642-00596-1_5
• ISSN: 0302-9743
• EISBN: 978-3-642-00596-1
• ISBN: 978-3-642-00595-4
• Language: English
• Keywords: bisimulation games; petri nets; modal and temporal logics; behavioural equivalences; concurrent and reactive systems