Undecidability of weak bisimilarity for pushdown processes

DOI10.1007/3-540-45694-5_38MaRDI QIDQ4484512zbMATH OpenFDO

Authors Jiří Srba

Publication date 12 June 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2421/24210579.htm

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Undecidability of weak bisimilarity for PA-processes
• Refining the undecidability border of weak bisimilarity
• Completeness results for undecidable bisimilarity problems
• Decidability of weak bisimilarity for a subset of basic parallel processes
• scientific article; zbMATH DE number 1232243

Cited in

(16)

• The complexity of bisimilarity-checking for one-counter processes.
• Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
• Completeness results for undecidable bisimilarity problems
• Refining the undecidability border of weak bisimilarity
• On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two
• Undecidability of bisimilarity by defender's forcing
• Undecidability of accordance for open systems with unbounded message queues
• Weak bisimilarity with infinite-state systems can be decided in polynomial time
• Undecidability of weak bisimilarity for PA-processes
• Undecidability of weak bisimulation equivalence for 1-counter processes
• scientific article; zbMATH DE number 2163042 (Why is no real title available?)
• Foundations of Software Science and Computation Structures
• On the computational complexity of bisimulation, redux
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes

This page was built for publication: Undecidability of weak bisimilarity for pushdown processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4484512)