Probabilistic length-reducing two-pushdown automata

DOI10.1007/s00224-007-9066-xzbMath1178.68319OpenAlexW1979270933MaRDI QIDQ841617

Tomasz Jurdziński

Publication date: 18 September 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9066-x

zbMATH Keywords

Monte Carlo lrTPDA

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Membership for growing context-sensitive grammars is polynomial
• Properties of probabilistic pushdown automata
• Growing context-sensitive languages and Church-Rosser languages
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Lower bound technique for length-reducing automata
• Church-Rosser Thue systems and formal languages
• Probabilistic Length-Reducing Automata
• On the power of Las Vegas II: Two-way finite automata