Weak bisimilarity and regularity of context-free processes is EXPTIME-hard

DOI10.1016/j.tcs.2004.10.008zbMath1078.68109OpenAlexW2063293762MaRDI QIDQ1763731

Richard Mayr

Publication date: 22 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.10.008

zbMATH Keywords

BPABisimulationPushdown automataContext-free processes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (3)

On the complexity of checking semantic equivalences between pushdown processes and finite-state processes ⋮ Unnamed Item ⋮ Bisimilarity on basic parallel processes

Cites Work

• Deciding bisimilarity is P-complete
• Decidability of bisimulation equivalence for normed pushdown processes
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Process rewrite systems.
• An elementary bisimulation decision procedure for arbitrary context-free processes
• Alternation
• Complexity of Weak Bisimilarity and Regularity for BPA and BPP
• High undecidability of weak bisimilarity for Petri nets
• A variant of a recursively unsolvable problem
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Weak bisimilarity and regularity of context-free processes is EXPTIME-hard