K + 1 heads are better than K
- 1 October 1976
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 67-70
- https://doi.org/10.1109/sfcs.1976.18
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.Keywords
This publication has 3 references indexed in Scilit:
- On 3-head versus 2-head finite automataActa Informatica, 1975
- Computation by multi-head finite automataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1971
- On Multi-Head Finite AutomataIBM Journal of Research and Development, 1966