Properties of probabilistic pushdown automata

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)

zbMATH Keywords

pushdown automatamodels of computationprobabilistic computationgames against natureArthur-Merlin gamesspace-bounded computation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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