Refining the Undecidability Border of Weak Bisimilarity | Zendy

Mojmír Křetínský | Zendy; Vojtěch Řehák | Zendy; Jan Strejček | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Refining the Undecidability Border of Weak Bisimilarity

Author(s) -

Mojmír Křetínský,

Vojtěch Řehák,

Jan Strejček

Publication year - 2006

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2005.11.014

Subject(s) - undecidable problem , decidability , multiset , bisimulation , equivalence (formal languages) , mathematics , discrete mathematics , process calculus , pushdown automaton , embedded pushdown automaton , computer science , theoretical computer science , finite state machine , algorithm , programming language , context free grammar , parsing , tree adjoining grammar

Weak bisimilarity is one of the most studied behavioural equivalences. This equivalence is undecidable for pushdown processes (PDA), process algebras (PA), and multiset automata (MSA, also known as parallel pushdown processes, PPDA). Its decidability is an open question for basic process algebras (BPA) and basic parallel processes (BPP). We move the undecidability border towards these classes by showing that the equivalence remains undecidable for weakly extended versions of BPA and BPP. In fact, we show that the weak bisimulation equivalence problem is undecidable even for normed subclasses of BPA and BPP extended with a finite constraint system

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research