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...
| Autor principal: | |
|---|---|
| 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 |