On probabilistic pushdown automata

DOI10.1016/J.IC.2009.11.001zbMath1205.68202OpenAlexW2140852079MaRDI QIDQ989292

Georg Schnitger, Juraj Hromkovič

Publication date: 19 August 2010

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2009.11.001

zbMATH Keywords

determinismrandomizationnondeterminismpushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (5)

Classical and Quantum Counter Automata on Promise Problems ⋮ QUANTUM COUNTER AUTOMATA ⋮ TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES ⋮ Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems ⋮ Computation with multiple CTCs of fixed length and width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
• Language recognition using probabilistic Turing machines in real time, and automata with a push-down store
• Projections of languages recognizable by probabilistic and alternating finite multitape automata
• On the distributional complexity of disjointness
• Properties of probabilistic pushdown automata
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions
• On the power of Las Vegas II: Two-way finite automata

This page was built for publication: On probabilistic pushdown automata