Properties of probabilistic pushdown automata

DOI10.1007/3-540-60249-6_66MaRDI QIDQ5055907zbMATH OpenOpenAlexFDO

Authors Ioan I. Macarie, Ogihara, Mitsunori

Publication date 9 December 2022

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60249-6_66

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Properties of probabilistic pushdown automata
• On probabilistic pushdown automata
• Discounted Properties of Probabilistic Pushdown Automata
• STACS 2005
• Methods for quantitative analysis of probabilistic pushdown automata
• Analyzing probabilistic pushdown automata
• Algebraic properties of probabilistic finite automata
• Decidable and expressive classes of probabilistic automata
• Decidable and expressive classes of probabilistic automata
• Bisimilarity of probabilistic pushdown automata

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• Alternating Pushdown and Stack Automata
• Alternating multihead finite automata
• Alternation
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Computational Complexity of Probabilistic Turing Machines
• Depth reduction for noncommutative arithmetic circuits
• On non-determinacy in simple computing devices
• On relativizing auxiliary pushdown machines
• On tape-bounded complexity classes and multihead finite automata
• On the Tape Complexity of Deterministic Context-Free Languages
• On the structure of log-space probabilistic complexity classes (extended abstract)
• Properties that characterize LOGCFL
• Transformational methods and their application to complexity problems. Corrigenda
• Tree-size bounded alternation

Cited in

(9)

• Analyzing probabilistic pushdown automata
• On the power of deep pushdown stacks
• One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity (preliminary report)
• Alternation bounded auxiliary pushdown automata
• Language equivalence of probabilistic pushdown automata
• scientific article; zbMATH DE number 3862469 (Why is no real title available?)
• Some modifications of auxiliary pushdown automata
• Advocating ownership
• On probabilistic pushdown automata

This page was built for publication: Properties of probabilistic pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5055907)