Refining the Undecidability Border of Weak Bisimilarity
by
Mojmír Křetínský,
Vojtěch Řehák,
Jan Strejček,
A full version of the paper presented at INFINITY 2005. August 2005, 20 pages.
FIMU-RS-2005-06.
Available as Postscript,
PDF.
Abstract:
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. Further, we show the results hold for even more
restricted classes of normed BPA with finite constraint system and normed
BPP with finite constraint system.