Some Accepting Powers of Bottom-Up Pyramid Cellular Acceptors with n-dimensional Layers

DOI

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 Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - JOUR
AU  - Makoto Sakamoto
AU  - Makoto Nagatomo
AU  - Tatsuma Kurogi
AU  - Satoshi Ikeda
AU  - Masahiro Yokomichi
AU  - Hiroshi Furutani
AU  - Takao Ito
AU  - Yasuo Uchida
AU  - Tsunehiro Yoshinaga
PY  - 2014
DA  - 2014/12/15
TI  - Some Accepting Powers of Bottom-Up Pyramid Cellular Acceptors with n-dimensional Layers
JO  - Journal of Robotics, Networking and Artificial Life
SP  - 189
EP  - 193
VL  - 1
IS  - 3
SN  - 2352-6386
UR  - https://doi.org/10.2991/jrnal.2014.1.3.4
DO  - 10.2991/jrnal.2014.1.3.4
ID  - Sakamoto2014
ER  -