Space-bounded probabilistic game automata

DOI10.1145/103516.128681zbMath0799.68095OpenAlexW2046176315MaRDI QIDQ4302843

Anne Condon

Publication date: 13 November 1994

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/103516.128681

zbMATH Keywords

nondeterminisminteractive proof systemsalternationprobabilistic computationrelations among complexity classesArthur-Merlin gamesbounded-action devicesprobabilistic game automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Fast approximate probabilistically checkable proofs, Random walks on colored graphs, Checking the correctness of memories, The complexity of debate checking, Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems, The complexity of the max word problem and the power of one-way interactive proof systems