Comparing verboseness for finite automata and Turing machines (Q705065)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Comparing verboseness for finite automata and Turing machines
scientific article

    Statements

    Comparing verboseness for finite automata and Turing machines (English)
    0 references
    0 references
    25 January 2005
    0 references
    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.
    0 references
    complexity classes
    0 references
    verboseness
    0 references
    finite automata
    0 references
    Turing machines
    0 references
    regular languages
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references