Finite state verifiers with constant randomness

DOI10.2168/LMCS-10(3:6)2014MaRDI QIDQ2878753zbMATH OpenOpenAlexFDO

Authors Cem Say, Abuzer Yakaryılmaz

Publication date 5 September 2014

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/lmcs-10(3:6)2014

zbMATH Keywords

constant randomnessinteractive proof systemsmultihead automataNLprobabilistic finite automatarandomness complexity

Mathematics Subject Classification ID

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

Recommendations

• Finite state verifiers with constant randomness
• Windable heads and recognizing \textsf{NL} with constant randomness
• Finite state verifiers I
• scientific article; zbMATH DE number 4045155
• Multi-oracle interactive protocols with constant space verifiers

Cited in

(13)

• Constant-space, constant-randomness verifiers with arbitrarily small error
• Improved constructions for succinct affine automata
• Affine automata verifiers
• Energy complexity of regular language recognition
• Real-time, constant-space, constant-randomness verifiers
• Finite state verifiers with constant randomness
• Classically time-controlled quantum automata
• Real-time, constant-space, constant-randomness verifiers
• Energy complexity of computation
• Classical and quantum Merlin-Arthur automata
• Unconditional proofs of quantumness between small-space machines
• \(\mathrm{P}\) has polynomial-time finite-state verifiers
• Short and useful quantum proofs for sublogarithmic-space verifiers

This page was built for publication: Finite state verifiers with constant randomness

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