Some Hierarchy Results on Multihead Automata over a One-Letter Alphabet

Yue WANG  Katsushi INOUE  Itsuo TAKANAMI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.6   pp.625-633
Publication Date: 1993/06/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automaton, Language and Theory of Computing
Keyword: 
sensing multihead automata,  automata on two-dimensional tapes,  one-letter alphabet,  hierarchy,  computational complexity,  

Full Text: PDF>>
Buy this Article




Summary: 
The hierarchies of multihead finite automata over a one-letter alphabet are investigated. Let SeH(k) [NSeH(k) ] denote the class of languages over a one-letter alphabet accepted by deterministic [nondeterministic] sensing two-way k-head finite automata. Let H (k)s[NH(k)s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way deterministic [nondeterministic] k-head finite automata. Let SeH(k)s[NSeH(k)s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way sensing deterministic [nondeterministic] k-head finite automata. This paper shows that SeH(k) SeH(k1) and NSeH(k) NSeH(k1) hold for all k3. It is also shown that H(k)s[NH(k)s] H(k1)s[NH (k1)s] and SeH (k)s[NSeH(k)s] SeH(k1)s[NSeH(k1)s] hold for all k1.