@Article{YR78,
  author = 	 { Andrew C. Yao and Ronald L. Rivest },
  title = 	 { $k+1$ heads are better than $k$ },
  pages = 	 { 337--340 },
  acmid =        { 322076 },  
  doi =          { 10.1145/322063.322076 },                  
  acm =          { 2424 },                  
  journal = 	 { JACM },
  OPTyear = 	 { 1978},
  OPTmonth = 	 { April },
  date =         { 1978-04 },                  
  volume = 	 { 25 },
  number = 	 { 2 },
  publisher =    { ACM },                  
  issn =         { 0004-5411 },
  keywords =     { multihead finite automata },                
  abstract =     {
                   There are languages which can be recognized by a deterministic
                   $(k+1)$-headed one-way finite automaton but which cannot be
                   recognized by a $k$-headed one-way (deterministic or nondeterministic)
                   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.                  
                 },
}