Journal of Robotics, Networking and Artificial Life

Volume 1, Issue 3, December 2014, Pages 189 - 193

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

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 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)

Journal
Journal of Robotics, Networking and Artificial Life
Volume-Issue
1 - 3
Pages
189 - 193
Publication Date
2014/12/15
ISSN (Online)
2352-6386
ISSN (Print)
2405-9021
DOI
https://doi.org/10.2991/jrnal.2014.1.3.4How to use a DOI?
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/).

Cite this article

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  - https://doi.org/10.2991/jrnal.2014.1.3.4
ID  - Sakamoto2014
ER  -