Comparing Verboseness for Finite Automata and Turing Machines |
| |
Authors: | Till Tantau |
| |
Affiliation: | (1) Fakultät IV — Elektrotechnik und Informatik, Technische Universität Berlin, Franklinstraße 28/29, D-10587 Berlin, Germany |
| |
Abstract: | A language is called (m,n)-verbose if there exists a Turing
machine that enumerates for any n words at most m possibilities
for their characteristic string. This notion is compared with
(m,n)-fa-verboseness, where instead of a Turing machine a
finite automaton is used. By use of a new diagonalisation method,
where finite automata trick Turing machines, it is shown that all
(m,n)-verbose languages are (h,k)-verbose iff all
(m,n)-fa-verbose languages are (h,k)-fa-verbose. In other words,
Turing machines and finite automata behave exactly the same way with
respect to inclusion of verboseness classes. This identical
behaviour implies that the nonspeedup theorem also holds for finite
automata. As an application of the theoretical framework, a lower
bound is derived on the number of bits that need to be communicated
to finite automata protocol checkers for nonregular protocols. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|