Authors
Makoto Sakamoto, Makoto Nagatomo, Tatsuma Kurogi, Satoshi Ikeda, Masahiro Yokomichi, Hiroshi Furutani, Takao Ito, Yasuo Uchida, Tsunehiro Yoshinaga
Corresponding Author
Makoto Sakamoto
Available Online 15 December 2014.
DOI
https://doi.org/10.2991/jrnal.2014.1.3.4How to use a DOI?
Keywords
cellular automaton, diameter, finite automaton, n-dimension, parallelism, pattern recognition, real time
Abstract
In theoretical computer science, the Turing machine was introduced as a simple mathematical model of computers in 1936, and has played a number of important roles in understanding and exploiting basic concepts and mechanisms in computing and information processing. After that, the development of the processing of pictorial information by computer was rapid in those days. Therefore, the problem of computational complexity was also arisen in the two-dimensional information processing. M.Blum and C.Hewitt first proposed two-dimensional automata as a computational model of two-dimensional pattern processing in 1967[1]. Since then, many researchers in this field have been investigating many properties of two- or three-dimensional automata. In 1997, C.R.Dyer and A.Rosenfeld introduced an acceptor on a two-dimensional pattern (or tape), called the pyramid cellular acceptor, and demonstrated that many useful recognition tasks are executed by pyramid cellular acceptors in time proportional to the logarithm of the diameter of the input. They also introduced a bottom-up pyramid cellular acceptor which is a restricted version of the pyramid cellular acceptor, and proposed some interesting open problems about bottom-up pyramid cellular acceptors. On the other hand, we think that the study of n-dimensional automata has been mean- ingful as the computational model of n-dimensional information processing[9]. In this paper, we investigate about bottom-up pyramid cellular accptors with n-dimensional layers, and show their some accepting powers.

Copyright
© 2013, the Authors. Published by ALife Robotics Corp. Ltd.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).