Properties of probabilistic pushdown automata

DOI10.1007/3-540-60249-6_66OpenAlexW1558302339MaRDI QIDQ5055907

Ogihara, Mitsunori, Ioan I. Macarie

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) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• 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