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

DOI10.1016/S0304-3975(03)00081-1zbMath1044.68099OpenAlexW2161891404MaRDI QIDQ1401395

Antonín 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)

Related Items

A generic framework for checking semantic equivalences between pushdown automata and finite-state automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An efficient automata approach to some problems on context-free grammars.
• A short proof of the decidability of bisimulation for normed BPA- processes
• Decidability of bisimulation equivalence for normed pushdown processes
• Characteristic formulae for processes with divergence
• Undecidable equivalences for basic process algebra
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Process rewrite systems.
• Decidability of bisimilarity for one-counter processes.
• Simulation preorder over simple process algebras
• Bisimulation equivalence is decidable for all context-free processes
• On the computational power of pushdown automata
• Decidability of bisimulation equivalence for process generating context-free languages
• Graphes canoniques de graphes algébriques
• An elementary bisimulation decision procedure for arbitrary context-free processes
• Process Algebra
• Actions speak louder than words: proving bisimilarity for context-free processes
• Deciding bisimulation-like equivalences with finite-state processes
• Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
• Reachability analysis of pushdown automata: Application to model-checking

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