Finite state verifiers with constant randomness

DOI10.2168/LMCS-10(3:6)2014zbMath1338.68084OpenAlexW1636875177MaRDI QIDQ2878753

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

interactive proof systemsprobabilistic finite automataNLrandomness complexitymultihead automataconstant randomness

Mathematics Subject Classification ID

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

Related Items (8)

Affine automata verifiers ⋮ Energy complexity of regular language recognition ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ Classically time-controlled quantum automata ⋮ Energy complexity of computation ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ Constant-space, constant-randomness verifiers with arbitrarily small error ⋮ Improved constructions for succinct affine automata

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