Language equivalence of probabilistic pushdown automata

DOI10.1016/j.ic.2014.04.003zbMath1360.68556OpenAlexW1990621328MaRDI QIDQ2252520

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

Publication date: 18 July 2014

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.04.003

zbMATH Keywords

language equivalencepushdown systemsprobabilistic systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Unnamed Item, Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems, Unnamed Item

Cites Work

• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• \(L(A)=L(B)\)? decidability results from complete formal systems
• Deciding probabilistic bisimilarity over infinite-state probabilistic systems
• Model Checking of Recursive Probabilistic Systems
• Bisimilarity of Probabilistic Pushdown Automata
• Runtime Analysis of Probabilistic Programs with Unbounded Recursion
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
• On the Complexity of Numerical Analysis
• Unary Pushdown Automata and Straight-Line Programs
• Matrix Equations and Normal Forms for Context-Free Grammars
• On Greibach normal form construction
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item