Decidability of bisimilarity for one-counter processes.

DOI10.1006/inco.1999.2813zbMath1046.68621OpenAlexW2060254679MaRDI QIDQ1854338

Petr Jančar

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1999.2813

zbMATH Keywords

pushdown automatabisimulation equivalence

Mathematics Subject Classification ID

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

Related Items

DP lower bounds for equivalence-checking and model-checking of one-counter automata ⋮ Bisimulation equivalence and regularity for real-time one-counter automata ⋮ The complexity of bisimilarity-checking for one-counter processes. ⋮ Nonprimitive recursive complexity and undecidability for Petri net equivalences ⋮ Simulation preorder over simple process algebras

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Undecidability of bisimilarity for Petri nets and some related problems
• Deterministic one-counter automata
• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• Bisimulation equivalence is decidable for all context-free processes
• Semigroups, Presburger formulas, and languages
• The equivalence problem for deterministic pushdown automata is decidable
• Petri nets, commutative context-free grammars, and basic parallel processes
• Decidability of bisimulation equivalence for normed pushdown processes
• Bisimulation collapse and the process taxonomy