Properties of probabilistic pushdown automata
From MaRDI portal
Publication:5055907
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)