Properties of probabilistic pushdown automata
From MaRDI portal
Publication:1274989
DOI10.1016/S0304-3975(98)00059-0zbMath0912.68136MaRDI QIDQ1274989
Ioan I. Macarie, Ogihara, Mitsunori
Publication date: 12 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
pushdown automatamodels of computationprobabilistic computationgames against natureArthur-Merlin gamesspace-bounded computation
Related Items (4)
Probabilistic length-reducing two-pushdown automata ⋮ On the power of randomized multicounter machines ⋮ Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems ⋮ On probabilistic pushdown automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multihead two-way probabilistic finite automata
- Alternating multihead finite automata
- Tree-size bounded alternation
- Properties that characterize LOGCFL
- On tape-bounded complexity classes and multihead finite automata
- Transformational methods and their application to complexity problems. Corrigenda
- On non-determinacy in simple computing devices
- Alternating Pushdown and Stack Automata
- Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
- On relativizing auxiliary pushdown machines
- Alternation
- Computational Complexity of Probabilistic Turing Machines
- On the Tape Complexity of Deterministic Context-Free Languages
- On the structure of log-space probabilistic complexity classes
- Depth reduction for noncommutative arithmetic circuits
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
This page was built for publication: Properties of probabilistic pushdown automata
