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

Yue WANG; Katsushi INOUE; Itsuo TAKANAMI

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

Yue WANG, Katsushi INOUE, Itsuo TAKANAMI

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E76-D No.6 pp.625-633

Publication Date: 1993/06/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Automaton, Language and Theory of Computing

Cite this

Copy

Yue WANG, Katsushi INOUE, Itsuo TAKANAMI, "Some Hierarchy Results on Multihead Automata over a One-Letter Alphabet" in IEICE TRANSACTIONS on Information, vol. E76-D, no. 6, pp. 625-633, June 1993, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e76-d_6_625/_p

Copy

@ARTICLE{e76-d_6_625,
author={Yue WANG, Katsushi INOUE, Itsuo TAKANAMI, },
journal={IEICE TRANSACTIONS on Information},
title={Some Hierarchy Results on Multihead Automata over a One-Letter Alphabet},
year={1993},
volume={E76-D},
number={6},
pages={625-633},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - Some Hierarchy Results on Multihead Automata over a One-Letter Alphabet
T2 - IEICE TRANSACTIONS on Information
SP - 625
EP - 633
AU - Yue WANG
AU - Katsushi INOUE
AU - Itsuo TAKANAMI
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E76-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 1993
AB - 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.
ER -