Game characterization of probabilistic bisimilarity, and applications to pushdown automata
DOI10.23638/LMCS-14(4:13)2018zbMATH Open1407.68252arXiv1711.06120MaRDI QIDQ4558784FDOQ4558784
Authors: Vojtech Forejt, Stefan Kiefer, Petr Jančar, James Worrell 
Publication date: 30 November 2018
Full work available at URL: https://arxiv.org/abs/1711.06120
Recommendations
- Bisimilarity of probabilistic pushdown automata
- Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems
- Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems
- CONCUR 2004 - Concurrency Theory
- Deciding probabilistic bisimilarity over infinite-state probabilistic systems
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Cites Work
- Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
- Title not available (Why is that?)
- Deciding bisimilarity and similarity for probabilistic processes.
- Verification on infinite structures.
- Pushdown processes: Games and model-checking
- Model Checking Probabilistic Pushdown Automata
- Branching bisimulation for probabilistic systems: characteristics and decidability
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
- On the complexity of computing probabilistic bisimilarity
- On emptiness and counting for alternating finite automata
- A note on emptiness for alternating finite automata with a one-letter alphabet
- Title not available (Why is that?)
- The Bisimulation Problem for Equational Graphs of Finite Out-Degree
- On the complexity of checking semantic equivalences between pushdown processes and finite-state processes
- Title not available (Why is that?)
- Bisimilarity on basic process algebra is in 2-ExpTime (an explicit proof)
- Probabilistic bisimulation for realistic schedulers
- Bisimilarity of one-counter processes is PSPACE-complete
- BPA bisimilarity is EXPTIME-hard
- Bisimulation Equivalence of First-Order Grammars
- Bisimilarity of Pushdown Automata is Nonelementary
- Equivalences of Pushdown Systems Are Hard
- Language equivalence of probabilistic pushdown automata
- Deciding probabilistic bisimilarity over infinite-state probabilistic systems
- Bisimilarity of Probabilistic Pushdown Automata
- Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems
- Beyond Language Equivalence on Visibly Pushdown Automata
- Bisimulation equivalence and regularity for real-time one-counter automata
Cited In (6)
- Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata
- Countdown games, and simulation on (succinct) one-counter nets
- Space-bounded probabilistic game automata
- Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems
- Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems
- Game equivalence and expressive power of game description languages: a bisimulation approach
This page was built for publication: Game characterization of probabilistic bisimilarity, and applications to pushdown automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558784)
