K+1 Heads are Better than K,
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 k-headed nondeterministic finite automaton which is accepted by no k-headed deterministic finite automaton. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1976
- Accession Number
- ADA030008
Entities
People
- Andrew C. Yao
- Ronald L. Rivest
Organizations
- Massachusetts Institute of Technology