Constant-space, constant-randomness verifiers with arbitrarily small error

DOI10.1016/j.ic.2021.104744OpenAlexW3037402156MaRDI QIDQ2084769

A. C. Cem Say, Mehmet Utkan Gezer

Publication date: 13 October 2022

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

interactive proof systemsprobabilistic finite automatamulti-head finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (2)

Real-time, constant-space, constant-randomness verifiers ⋮ Special issue: Selected papers of the 14th international conference on language and automata theory and applications, LATA 2020

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of debate checking
• Descriptional and computational complexity of finite automata -- a survey
• Complexity of multi-head finite automata: origins and directions
• Windable heads and recognizing \textsf{NL} with constant randomness
• An application of quantum finite automata to interactive proof systems
• Multi-oracle interactive protocols with constant space verifiers
• The complexity of the max word problem and the power of one-way interactive proof systems
• Interactive proof systems with polynomially bounded strategies
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Interactive proofs with quantum finite automata
• On non-determinacy in simple computing devices
• Finite state verifiers with constant randomness
• Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
• A time-space tradeoff for language recognition
• Finite state verifiers I
• Debates with Small Transparent Quantum Verifiers

This page was built for publication: Constant-space, constant-randomness verifiers with arbitrarily small error