Windable heads and recognizing \textsf{NL} with constant randomness

DOI10.1007/978-3-030-40608-0_12MaRDI QIDQ782573zbMATH OpenOpenAlexFDO

Authors Mehmet Utkan Gezer

Publication date 27 July 2020

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

zbMATH Keywords

interactive proof systemsmulti-head finite automataprobabilistic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Abstract: Every language in NL has a $k$-head two-way nondeterministic finite automaton (2nfa($k$)) recognizing it. It is known how to build a constant-space verifier algorithm from a 2nfa($k$) for the same language with constant-randomness, but with error probability $frac{k}^2-12k^2$ that can not be reduced further by repetition. We have defined the unpleasant characteristic of the heads that causes the high error as the property of being "windable". With a tweak on the previous verification algorithm, the error is improved to $frac{k}_{extrmW}^2-12k_{extrmW}^2$, where $k_{extrmW}lek$ is the number of windable heads. Using this new algorithm, a subset of languages in NL that have a 2nfa($k$) recognizer with $k_{extrmW}le1$ can be verified with arbitrarily reducible error using constant space and randomness.

Recommendations

• scientific article; zbMATH DE number 1949663
• NL-printable sets and nondeterministic Kolmogorov complexity
• NL-printable sets and nondeterministic Kolmogorov complexity
• Power of randomization in automata on infinite strings
• Power of Randomization in Automata on Infinite Strings
• On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
• Fooling a two-way nondeterministic multihead automaton with reversal number restriction
• Probabilistic Turing machines and recursively enumerable Dedekind cuts
• A computable version of the random signs problem and Kolmogorov complexity

Cited in

(3)

• Constant-space, constant-randomness verifiers with arbitrarily small error
• Finite state verifiers with constant randomness
• Finite state verifiers with constant randomness

This page was built for publication: Windable heads and recognizing \textsf{NL} with constant randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782573)