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

Technology reports of the Yamaguchi University Volume 2 Issue 3 Page 301-306

published_at 1979-12

KJ00004350998.pdf

[fulltext] 420 KB

Title

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

Creators Inoue Katsushi

Creators Takanami Itsuo

Source Identifiers

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.

Subjects

工学 ( Other)

Languages eng

Resource Type departmental bulletin paper

Publishers 山口大学工学部

Date Issued 1979-12

File Version Version of Record

Access Rights open access

Relations

[ISSN]0386-3433

[NCID]AA0086073X

Schools 工学部