Technology reports of the Yamaguchi University

Back to Top

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

A note on bottom-up pyramid acceptors

A note on bottom-up pyramid acceptors
Inoue Katsushi
Takanami Itsuo
fulltext
266 KB
KJ00004350985.pdf
Descriptions
In this paper, we investigate the relationship between the accepting powers of deterministic bottom-up pyramid acceptors and deterministic two-dimensional finite automata, and show that there is a set accepted by a deterministic two-dimensional finite automaton but not by any deterministic bottom-up pyramid acceptor which operates in time of order lower than the diameter of the input, and vice versa.