Probabilistic length-reducing two-pushdown automata

DOI10.1007/S00224-007-9066-XMaRDI QIDQ841617zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Probabilistic Length-Reducing Automata
• On probabilistic pushdown automata
• scientific article; zbMATH DE number 2087229
• scientific article; zbMATH DE number 2038700
• scientific article; zbMATH DE number 1405658

Cites work

• Church-Rosser Thue systems and formal languages
• Growing context-sensitive languages and Church-Rosser languages
• scientific article; zbMATH DE number 1962823 (Why is no real title available?)
• scientific article; zbMATH DE number 2038700 (Why is no real title available?)
• scientific article; zbMATH DE number 2087236 (Why is no real title available?)
• scientific article; zbMATH DE number 1408346 (Why is no real title available?)
• Lower bound technique for length-reducing automata
• Membership for growing context-sensitive grammars is polynomial
• On the power of Las Vegas II: Two-way finite automata
• Probabilistic Length-Reducing Automata
• Properties of probabilistic pushdown automata
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages

Cited in

(4)

• scientific article; zbMATH DE number 2087229 (Why is no real title available?)
• Probabilistic Length-Reducing Automata
• On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
• On probabilistic pushdown automata

This page was built for publication: Probabilistic length-reducing two-pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q841617)