K+1 Heads are Better Than K
dc.contributor.author | Yao, Andrew C. | en_US |
dc.contributor.author | Rivest, Ronald L. | en_US |
dc.date.accessioned | 2023-03-29T14:07:03Z | |
dc.date.available | 2023-03-29T14:07:03Z | |
dc.date.issued | 1976-09 | |
dc.identifier.uri | https://hdl.handle.net/1721.1/148903 | |
dc.description.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 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. | en_US |
dc.relation.ispartofseries | MIT-LCS-TM-075 | |
dc.title | K+1 Heads are Better Than K | en_US |
dc.identifier.oclc | 3135408 |