scientific article; zbMATH DE number 6987092

DOI10.23638/LMCS-14(4:13)2018zbMath1407.68252arXiv1711.06120MaRDI QIDQ4558784

Stefan Kiefer, Vojtěch Forejt, Petr Jančar, James Worrell

Publication date: 30 November 2018

Full work available at URL: https://arxiv.org/abs/1711.06120

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

pushdown automataprobabilistic bisimulation equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (2)

Countdown games, and simulation on (succinct) one-counter nets ⋮ Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes
• Probabilistic bisimulation for realistic schedulers
• Pushdown processes: Games and model-checking
• BPA bisimilarity is EXPTIME-hard
• Deciding bisimilarity and similarity for probabilistic processes.
• Language equivalence of probabilistic pushdown automata
• A note on emptiness for alternating finite automata with a one-letter alphabet
• Deciding probabilistic bisimilarity over infinite-state probabilistic systems
• Branching bisimulation for probabilistic systems: characteristics and decidability
• Bisimulation equivalence and regularity for real-time one-counter automata
• On the Complexity of Computing Probabilistic Bisimilarity
• Deciding Probabilistic Simulation between Probabilistic Pushdown Automata and Finite-State Systems
• Bisimilarity of Probabilistic Pushdown Automata
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
• Bisimilarity of One-Counter Processes Is PSPACE-Complete
• Beyond Language Equivalence on Visibly Pushdown Automata
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)
• Bisimulation Equivalence of First-Order Grammars
• Bisimilarity of Pushdown Automata is Nonelementary
• Model Checking Probabilistic Pushdown Automata
• The Bisimulation Problem for Equational Graphs of Finite Out-Degree
• Equivalences of Pushdown Systems Are Hard

This page was built for publication: