The complexity of probabilistic versus deterministic finite automata

DOI10.1007/BFB0009499zbMath1512.68133MaRDI QIDQ6487443

Andris Ambainis

Publication date: 25 January 2023

Mathematics Subject Classification ID

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

Related Items (3)

Complexity of Promise Problems on Classical and Quantum Automata ⋮ Artin’s Conjecture and Size of Finite Probabilistic Automata ⋮ Improved constructions for succinct affine automata

Cites Work

• Some aspects of probabilistic automata
• Probabilistic automata

This page was built for publication: The complexity of probabilistic versus deterministic finite automata