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.4
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/).