Technology reports of the Yamaguchi University

Back to Top

Technology reports of the Yamaguchi University Volume 2 Issue 3
published_at 1979-12

A note on decision problems for three-way two-dimensional finite automata

A note on decision problems for three-way two-dimensional finite automata
Inoue Katsushi
Takanami Itsuo
fulltext
420 KB
KJ00004350998.pdf
Descriptions
This note investigates some decision problems for three-way two-dimensional finite automata. It is shown, for example, that (1) the emptiness problem for nondeterministic three-way two-dimensional finite automata over a one-letter alphabet is solvable, (2) the universe problem for deterministic three-way two-dimensional finite automata over a one-letter alphabet is solvable, and (3) the universe, containment, and equivalence problems for non-deterministic three-way two-dimensional finite automata are unsolvable.