No label defined (Q3976039)

The main result of this paper is that languages recognizable in \(0(\log\log n)\) space must be regular. Let a probabilistic one-way Turingmachine be a Turingmachine with a one- way read-only input tape, a single scratch tape, whose choice of transition at each step is determined by the output of a random number generator. Say that such a machine \(M\) recognizes a language \(L\subset X^*\) in \(g(n)\) space with probability \(p\) if for all \(n\) and all \(w\in X^*\) of length \(n\) or less the probability is at least \(p\) that the machine halts after a finite number of steps, and that no more than \(g(n)\) squares on the scratch tape have been used, and that the machine has halted in either an accepting state or a rejecting state. Then one says that \(M\) recognized the language \(L\) in \(g(n)\) space with isolated cut point if there is a probability \(p>1/2\) such that \(M\) recognizes \(L\) in \(g(n)\) space with probability \(p\). It has been previously proved that no deterministic one-way Turingmachine can recognize nonregular languages in \(O(\log n)\) space (\textit{R. E. Stearns}), that there is a nonregular language recognizable in \(O(\log\log n)\) space by a probabilistic one-way Turingmachine (\textit{R. Freivalds}, and that any language recognized in \(O(\log\log n)\) space by a probabilistic one-way Turingmachine with probability at least \(2/3\) must be regular (\textit{R. Freivalds}). This paper extends those results with the following theorem. Theorem. A language recognized by a probabilistic one-way Turingmachine with probability \(1/2+\delta\) with \(\delta>0\) in \(O(\log\log n)\) space mut be regular. The theorem in turn depends on a crucial lemma which establishes for nonregular languages a lower bound on the rank of the members of a collection of relations related to the syntactic congruence. Specifically, for a language \(L\subset X^*\) say that two words \(w\) and \(w'\) are \(n\)-similar if for all \(v\in X^*\) such that \(wv\in X^{\leq n}\) and \(w'v\in X^{\leq n}\) imply that \(wv\in L\iff w'v\in L\). Then \(r_{sim}(L,X^{\leq n})\) is the rank of that relation restricted to \(X^{\leq n}\). Then the lemma is as follows. Lemma. If \(L\subseteq X^*\) is a non-regular language, then for infinitely many \(n\) \(r_{sim}(L,X^{\leq n})\geq \lfloor(n+3)/2\rfloor\). For the entire collection see [Zbl 0796.68140].