Comparing verboseness for finite automata and Turing machines (Q705065): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00224-003-1108-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2071094043 / rank | |||
Normal rank |
Latest revision as of 19:38, 19 March 2024
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
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