The complexity of bisimilarity-checking for one-counter processes.
From MaRDI portal
Recommendations
Cites work
- 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 automata approach to some problems on context-free grammars
- 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
- Efficient algorithms for model checking pushdown systems
- Equivalence-checking with one-counter automata: A generic method for proving lower bounds
- Graphes canoniques de graphes algébriques
- 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 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1142326 (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?)
- Model checking CTL properties of pushdown systems
- On simulation-checking with sequential systems
- On the complexity of bisimulation problems for pushdown automata
- On the complexity of semantic equivalences for pushdown automata and BPA
- On the computational power of pushdown automata
- Process Algebra
- Process rewrite systems.
- Reachability analysis of pushdown automata: Application to model-checking
- Simulation and bisimulation over one-counter processes
- Simulation is decidable for one-counter nets (extended abstract)
- Simulation preorder over simple process algebras
- Simulation problems for one-counter machines
- Strong bisimilarity and regularity of basic process algebra is PSPACE-hard
- The linear time -- branching time spectrum. I: The semantics of concrete, sequential processes.
- Undecidability of weak bisimilarity for pushdown 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
- Decidability of bisimilarity for one-counter processes.
- 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
- Bisimulation equivalence and regularity for real-time one-counter automata
- Efficient verification algorithms for one-counter processes
- On simulation-checking with sequential systems
- Complexity of checking bisimilarity between sequential and parallel processes
- Bisimilarity of one-counter processes is PSPACE-complete
- Undecidability of weak bisimulation equivalence for 1-counter processes
- Bisimulation equivalence is decidable for one-counter processes
- Equivalence-checking with one-counter automata: A generic method for proving lower bounds
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)
