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

概要

論文の詳細を見る
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(k+1) and NSeH(k)≠^^⊂NSeH(k+1) hold for all k≧3. It is also shown that H(k)^s[NH(k)^s]≠^^⊂H(k+1)^s[NH(k+1)^s] and SeH(k)^s[NSeH(k)^s]≠^^⊂SeH(k+1)^s[NSeH(k+1)^s] hold for all k≧1.
社団法人電子情報通信学会の論文
1993-06-25