Title :
K + 1 heads are better than K
Author :
Yao, Andrew C. ; Rivest, Ronald L.
Abstract :
There are languages which can be recognized by a deterministic (k + 1)-headed oneway finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, there is a language accepted by a 2-headed nondeterministic finite automaton which is accepted by no k-headed deterministic finite automaton.
Keywords :
Automata; Automatic control; Computer science; Contracts; Doped fiber amplifiers; Laboratories; Mathematics;
Conference_Titel :
Foundations of Computer Science, 1976., 17th Annual Symposium on
Conference_Location :
Houston, TX, USA
DOI :
10.1109/SFCS.1976.18
