Three-dimensional multicounter auaomata

Three-dimensional multicounter auaomata

Creators Sakamoto Makoto

Creators Inoue Katsushi

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.

[ISSN]0386-3433

[NCID]AA0086073X