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

DOI10.1007/978-3-031-07469-1_17OpenAlexW4281687983MaRDI QIDQ2164756

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

Publication date: 16 August 2022

Full work available at URL: https://arxiv.org/abs/2206.00968

zbMATH Keywords

interactive proof systemsprobabilistic finite automatareal-time finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Energy complexity of computation ⋮ Real-time, constant-space, constant-randomness verifiers

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
• 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

This page was built for publication: Real-time, constant-space, constant-randomness verifiers