Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Decidability of Branching Bisimulation on Normed Commutative Context-Free Processes
verfasst von : Wojciech Czerwiński, Piotr Hofman, Sławomir Lasota
Erschienen in: CONCUR 2011 – Concurrency Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We investigate normed commutative context-free processes (Basic Parallel Processes). We show that branching bisimilarity admits the
small response property
: in the Bisimulation Game, Duplicator always has a response leading to a process of size linearly bounded with respect to the Spoiler’s process. The linear bound is effective, which leads to decidability of branching bisimilarity. For weak bisimilarity, we are able merely to show existence of some linear bound, which is not sufficient for decidability. We conjecture however that the same effective bound holds for weak bisimilarity as well. We believe that further elaboration of novel techniques developed in this paper may be sufficient to demonstrate decidability.