Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs

Hisao HIRAKAWA; Katsushi INOUE; Akira ITO

doi:10.1093/ietisy/e88-d.1.31

Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs

Hisao HIRAKAWA, Katsushi INOUE, Akira ITO

Full Text Views

0

Share
Cite this

Summary :

Inoue et al. introduced an automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape by scanning the tape from various sides by various automata which move one way, and investigated the accepting power of such an automaton. This paper continues the investigation of this type of automata, especially, -type automata (obtained by combining four three-way two-dimensional deterministic finite automata (tr2-dfa's) in "or" fashion) and -type automata (obtained by combining four tr2-dfa's in "and" fashion). We first investigate a relationship between the accepting powers of -type automata and -type automata, and show that they are incomparable. Then, we investigate a hierarchy of the accepting powers based on the number of tr2-dfa's combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining three-way two-dimensional deterministic and nondeterministic finite automata.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.1 pp.31-38

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.1.31

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category

Cite this

Copy

Hisao HIRAKAWA, Katsushi INOUE, Akira ITO, "Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 1, pp. 31-38, January 2005, doi: 10.1093/ietisy/e88-d.1.31.
Abstract: Inoue et al. introduced an automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape by scanning the tape from various sides by various automata which move one way, and investigated the accepting power of such an automaton. This paper continues the investigation of this type of automata, especially, -type automata (obtained by combining four three-way two-dimensional deterministic finite automata (tr2-dfa's) in "or" fashion) and -type automata (obtained by combining four tr2-dfa's in "and" fashion). We first investigate a relationship between the accepting powers of -type automata and -type automata, and show that they are incomparable. Then, we investigate a hierarchy of the accepting powers based on the number of tr2-dfa's combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining three-way two-dimensional deterministic and nondeterministic finite automata.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.1.31/_p

Copy

@ARTICLE{e88-d_1_31,
author={Hisao HIRAKAWA, Katsushi INOUE, Akira ITO, },
journal={IEICE TRANSACTIONS on Information},
title={Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs},
year={2005},
volume={E88-D},
number={1},
pages={31-38},
abstract={Inoue et al. introduced an automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape by scanning the tape from various sides by various automata which move one way, and investigated the accepting power of such an automaton. This paper continues the investigation of this type of automata, especially, -type automata (obtained by combining four three-way two-dimensional deterministic finite automata (tr2-dfa's) in "or" fashion) and -type automata (obtained by combining four tr2-dfa's in "and" fashion). We first investigate a relationship between the accepting powers of -type automata and -type automata, and show that they are incomparable. Then, we investigate a hierarchy of the accepting powers based on the number of tr2-dfa's combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining three-way two-dimensional deterministic and nondeterministic finite automata.},
keywords={},
doi={10.1093/ietisy/e88-d.1.31},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs
T2 - IEICE TRANSACTIONS on Information
SP - 31
EP - 38
AU - Hisao HIRAKAWA
AU - Katsushi INOUE
AU - Akira ITO
PY - 2005
DO - 10.1093/ietisy/e88-d.1.31
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2005
AB - Inoue et al. introduced an automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape by scanning the tape from various sides by various automata which move one way, and investigated the accepting power of such an automaton. This paper continues the investigation of this type of automata, especially, -type automata (obtained by combining four three-way two-dimensional deterministic finite automata (tr2-dfa's) in "or" fashion) and -type automata (obtained by combining four tr2-dfa's in "and" fashion). We first investigate a relationship between the accepting powers of -type automata and -type automata, and show that they are incomparable. Then, we investigate a hierarchy of the accepting powers based on the number of tr2-dfa's combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining three-way two-dimensional deterministic and nondeterministic finite automata.
ER -