@InProceedings{YR76, replaced-by = { YR78 }, author = { Andrew C. Yao and Ronald L. Rivest }, title = { {$K+1$} heads are better than {$K$} }, pages = { 67--70 }, date = { 1976 }, doi = { 10.1109/SFCS.1976.18 }, booktitle = { Proceedings 17th Annual Symposium on Foundations of Computer Science }, publisher = { IEEE }, editor = { Michael J. Fischer }, eventtitle = { FOCS '76 }, OPTyear = { 1976 }, OPTmonth = { October 25--27, }, eventdate = { 1976-10-25/1976-10-27 }, venue = { Houston, Texas }, OPTorganization = { IEEE }, 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. }, }