Real-time, constant-space, constant-randomness verifiers

DOI10.1016/j.tcs.2023.114155MaRDI QIDQ6077068

A. C. Cem Say, Özdeniz Dolu, Nevzat Ersoy, Mehmet Utkan Gezer

Publication date: 17 October 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

multihead finite automatarandomized finite automatareal-time verifiers

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• The complexity of debate checking
• Complexity of multi-head finite automata: origins and directions
• On 3-head versus 2-head finite automata
• Interactive proof systems with polynomially bounded strategies
• Constant-space, constant-randomness verifiers with arbitrarily small error
• Real-time, constant-space, constant-randomness verifiers
• Set Automata
• Finite state verifiers with constant randomness
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• k + 1 Heads Are Better than k
• Computational Complexity
• On Multi-Head Finite Automata