Cargando…

Windable Heads and Recognizing NL with Constant Randomness

Every language in NL has a k-head two-way nondeterministic finite automaton (2nfa([Formula: see text])) recognizing it. It is known how to build a constant-space verifier algorithm from a 2nfa([Formula: see text]) for the same language with constant-randomness, but with error probability [Image: see...

Descripción completa

Detalles Bibliográficos
Autor principal: Gezer, Mehmet Utkan
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206657/
http://dx.doi.org/10.1007/978-3-030-40608-0_12