Simulation and bisimulation over one-counter processes

DOI10.1007/3-540-46541-3_28MaRDI QIDQ4501545zbMATH OpenFDO

Authors Petr Jančar, Antonin Kučera, Faron Moller

Publication date 4 September 2000

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

Full work available at URL https://doi.org/10.1007/3-540-46541-3_28

zbMATH Keywords

bisimulation problems over one-counter automata

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Simulation is decidable for one-counter nets (extended abstract)
• Simulation problems over one-counter nets
• Simulation problems for one-counter machines
• Bisimulation equivalence is decidable for one-counter processes
• Simulation over one-counter nets is PSPACE-complete

Cited in

(20)

• The complexity of bisimilarity-checking for one-counter processes.
• EXPSPACE-complete variant of countdown games, and simulation on succinct one-counter nets
• Simulation preorder over simple process algebras
• DP lower bounds for equivalence-checking and model-checking of one-counter automata
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• A general approach to comparing infinite-state systems with their finite-state specifications
• Trace inclusion for one-counter nets revisited
• Bisimulation equivalence and regularity for real-time one-counter automata
• On simulation-checking with sequential systems
• Simulation problems over one-counter nets
• Constrained simulations, nested simulation semantics and counting bisimulations
• Simulation over one-counter nets is PSPACE-complete
• Trace inclusion for one-counter nets revisited
• Process Bisimulation Via a Graphical Encoding
• Simulation is decidable for one-counter nets (extended abstract)
• Simulation problems for one-counter machines
• Bisimulation equivalence is decidable for one-counter processes
• scientific article; zbMATH DE number 2087430 (Why is no real title available?)
• Decidability of weak simulation on one-counter nets
• Countdown games, and simulation on (succinct) one-counter nets

This page was built for publication: Simulation and bisimulation over one-counter processes

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