The complexity of bisimilarity-checking for one-counter processes.

DOI10.1016/S0304-3975(03)00081-1MaRDI QIDQ1401395zbMATH OpenOpenAlexFDO

Authors Antonin Kučera

Publication date 17 August 2003

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

Full work available at URL https://doi.org/10.1016/s0304-3975(03)00081-1

zbMATH Keywords

BisimilarityOne-counter automataOne-counter nets

Mathematics Subject Classification ID

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

Recommendations

• Publication:2754154
• Bisimilarity of one-counter processes is PSPACE-complete
• Decidability of bisimilarity for one-counter processes.
• Publication:4501545
• Publication:4449204

Cites work

• scientific article; zbMATH DE number 1670780 (Why is no real title available?)
• scientific article; zbMATH DE number 1696434 (Why is no real title available?)
• scientific article; zbMATH DE number 3885321 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 1304996 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1101595 (Why is no real title available?)
• scientific article; zbMATH DE number 1142326 (Why is no real title available?)
• scientific article; zbMATH DE number 2080197 (Why is no real title available?)
• scientific article; zbMATH DE number 1927587 (Why is no real title available?)
• scientific article; zbMATH DE number 1490007 (Why is no real title available?)
• scientific article; zbMATH DE number 1500527 (Why is no real title available?)
• scientific article; zbMATH DE number 1759489 (Why is no real title available?)
• scientific article; zbMATH DE number 1929958 (Why is no real title available?)
• scientific article; zbMATH DE number 2086665 (Why is no real title available?)
• scientific article; zbMATH DE number 2087430 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 2242594 (Why is no real title available?)
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• A short proof of the decidability of bisimulation for normed BPA- processes
• Actions speak louder than words: proving bisimilarity for context-free processes
• An efficient automata approach to some problems on context-free grammars.
• An elementary bisimulation decision procedure for arbitrary context-free processes
• Bisimulation equivalence is decidable for all context-free processes
• Characteristic formulae for processes with divergence
• Decidability of bisimilarity for one-counter processes.
• Decidability of bisimulation equivalence for normed pushdown processes
• Decidability of bisimulation equivalence for process generating context-free languages
• Deciding bisimulation-like equivalences with finite-state processes
• Graphes canoniques de graphes algébriques
• On the computational power of pushdown automata
• Process Algebra
• Process rewrite systems.
• Reachability analysis of pushdown automata: Application to model-checking
• Simulation preorder over simple process algebras
• The linear time -- branching time spectrum. I: The semantics of concrete, sequential processes.
• Undecidable equivalences for basic process algebra
• Verification on infinite structures.
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time

Cited in

(12)

• A complexity analysis of bisimilarity for value-passing processes
• Complexity of checking bisimilarity between sequential and parallel processes
• Bisimulation equivalence and regularity for real-time one-counter automata
• scientific article; zbMATH DE number 1670834 (Why is no real title available?)
• scientific article; zbMATH DE number 2038739 (Why is no real title available?)
• Bisimulation equivalence is decidable for one-counter processes
• scientific article; zbMATH DE number 1696434 (Why is no real title available?)
• scientific article; zbMATH DE number 2087430 (Why is no real title available?)
• DP lower bounds for equivalence-checking and model-checking of one-counter automata
• Bisimilarity of one-counter processes is PSPACE-complete
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Decidability of bisimilarity for one-counter processes.

This page was built for publication: The complexity of bisimilarity-checking for one-counter processes.

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