Game characterization of probabilistic bisimilarity, and applications to pushdown automata

DOI10.23638/LMCS-14(4:13)2018MaRDI QIDQ4558784zbMATHFDO

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

zbMATH Keywords

pushdown automataprobabilistic bisimulation equivalence

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 2038739 (Why is no real title available?)
• scientific article; zbMATH DE number 1759621 (Why is no real title available?)
• scientific article; zbMATH DE number 1929958 (Why is no real title available?)
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• A note on emptiness for alternating finite automata with a one-letter alphabet
• BPA bisimilarity is EXPTIME-hard
• Beyond Language Equivalence on Visibly Pushdown Automata
• Bisimilarity of one-counter processes is PSPACE-complete
• Bisimilarity of probabilistic pushdown automata
• Bisimilarity of pushdown automata is nonelementary
• Bisimilarity on basic process algebra is in 2-ExpTime (an explicit proof)
• Bisimulation Equivalence of First-Order Grammars
• Bisimulation equivalence and regularity for real-time one-counter automata
• Branching bisimulation for probabilistic systems: characteristics and decidability
• Deciding bisimilarity and similarity for probabilistic processes.
• Deciding probabilistic bisimilarity over infinite-state probabilistic systems
• Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems
• Equivalences of Pushdown Systems Are Hard
• Language equivalence of probabilistic pushdown automata
• Model Checking Probabilistic Pushdown Automata
• On emptiness and counting for alternating finite automata
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes
• On the complexity of computing probabilistic bisimilarity
• Probabilistic bisimulation for realistic schedulers
• Pushdown processes: Games and model-checking
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
• The Bisimulation Problem for Equational Graphs of Finite Out-Degree
• Verification on infinite structures.

Cited in

(8)

• Countdown games, and simulation on (succinct) one-counter nets
• Game equivalence and expressive power of game description languages: a bisimulation approach
• Bisimilarity of probabilistic pushdown automata
• Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems
• Bisimilarity of pushdown automata is nonelementary
• Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems
• Space-bounded probabilistic game automata
• Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata

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)