Comparing verboseness for finite automata and Turing machines (Q705065): Difference between revisions

A language \(L\) is \((m, n)\)-verbose if there is a Turing machine that for any given \(n\) input words prints at most \(m\) strings of \(n\) bits one of which correctly shows which of the words belong to \(L\). Let \(V(m, n)\) denote the class of all \((m, n)\)-verbose languages. Hence, \(V(2^n, n)\) contains all languages while \(V(1, n)\) consists of the recursive languages \((n\geq 1)\). The polynomial-time verboseness classes \(V_p(m, n)\) are obtained by restricting the machines to work in polynomial time. The author defines the corresponding finite automaton verboseness classes \(V_{fa}(m, n)\) via multitape finite automata that read the \(n\) input words in parallel. The inclusion hierarchy of the classes \(V_{fa}(m, n)\) is studied and compared with the corresponding hierarchies of the classes \(V(m, n)\) and \(V_p(m, n)\). The main result is that \(V_{fa}(m, n)\subseteq V_{fa}(h, k)\) iff \(V(m, n)\subseteq V(h, k)\) for any \(m\), \(n\), \(h\) and \(k\). From this fact the author derives a non-speedup theorem for finite automata and, as a corollary of this, a lower bound on the number of bits to be communicated to finite automata checking non-regular protocols.