On the Power of Finite Automata with both Nondeterministic and Probabilistic States

DOI10.1137/S0097539794265578zbMath0911.68049OpenAlexW2077968161MaRDI QIDQ4388897

Anne Condon, Avi Wigderson, Samuel Pottle, Lisa Hellerstein

Publication date: 10 May 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794265578

zbMATH Keywords

Hankel matricesinteractive proof systemsArthur-Merlin gamesmatrix tilingnondeterministic probabilistic finite automata

Mathematics Subject Classification ID

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

Related Items

Affine automata verifiers, On some variations of two-way probabilistic finite automata models, A limit theorem for sets of stochastic matrices., Debates with Small Transparent Quantum Verifiers, Interactive proofs with quantum finite automata, An application of quantum finite automata to interactive proof systems