Browsing LCS Technical Memos (1974 - 2003) by Author "Yao, Andrew C."

Now showing items 1-1 of 1

    • K+1 Heads are Better Than K 

      Yao, Andrew C.; Rivest, Ronald L. (1976-09)
      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 non-deterministic) finite automaton. Furthermore, ...