Technology reports of the Yamaguchi University

Back to Top

Technology reports of the Yamaguchi University Volume 5 Issue 5
published_at 1996-12

Three-dimensional multicounter auaomata

Three-dimensional multicounter auaomata
Sakamoto Makoto
Inoue Katsushi
fulltext
678 KB
KJ00004351186.pdf
Descriptions
This paper introduces a three-dimensional multicounter automaton whose input tapes are restricted to cubic ones, and investigates some of its properties. We first show the difference between the accepting powers of five-way and six-way three-dimensional multicounter automata, and between the accepting powers of deterministic and nondeterministic five-way three-dimensional multicounter automata. We then show that hierarchies can be obtained by varying the number of counters or the amount of space allowed, for classes of sets accepted by five-way three-dimensional multicounter automata.