Properties of probabilistic pushdown automata
DOI10.1007/3-540-60249-6_66OpenAlexW1558302339MaRDI QIDQ5055907FDOQ5055907
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
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- On non-determinacy in simple computing devices
- Alternation
- Computational Complexity of Probabilistic Turing Machines
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- On tape-bounded complexity classes and multihead finite automata
- Alternating multihead finite automata
- Properties that characterize LOGCFL
- On the Tape Complexity of Deterministic Context-Free Languages
- Alternating Pushdown and Stack Automata
- Tree-size bounded alternation
- Transformational methods and their application to complexity problems. Corrigenda
- On relativizing auxiliary pushdown machines
- On the structure of log-space probabilistic complexity classes (extended abstract)
- Depth reduction for noncommutative arithmetic circuits
Cited In (9)
- Advocating ownership
- On probabilistic pushdown automata
- Language equivalence of probabilistic pushdown automata
- 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
- Title not available (Why is that?)
- Some modifications of auxiliary 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)
