Journal of Robotics, Networking and Artificial Life

Volume 1, Issue 3, December 2014, Pages 203 - 206

Homogeneous Systolic Pyramid Automata 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
10.2991/jrnal.2014.1.3.7How to use a DOI?
Keywords
cellular automaton, diameter, finite automaton, n-dimension, parallelism, pattern recognition, real time
Abstract

Cellular automata were investigated not only in the viewpoint of formal language theory, but also in the viewpoint of pattern recognition. Cellular automata can be classified into some types. A systolic pyramid automata is also one parallel model of various cellular automata. A homogeneous systolic pyramid automaton with n-dimensional layers (n-HSPA) is a pyramid stack of n-dimensional arrays of cells in which the bottom n-dimensional layer (level 0) has size an (a?1), the next lowest (a-1)n, and so forth, the (a-1)st n-dimensional layer (level (a-1)) consisting of a single cell, called the root. Each cell means an identical finite-state machine. The input is accepted if and only if the root cell ever enters an accepting state. An n-HSPA is said to be a real-time n-HSPA if for every n-dimensional tape of size an (a?1) it accepts the n-dimensional tape in time a-1. Moreover, a 1- way n-dimensional cellular automaton (1-nCA) can be considered as a natural extension of the 1-way two- dimensional cellular automaton to n-dimension. The initial configuration is accepted if the last special cell reaches a final state. A 1-nCA is said to be a real- time 1-nCA if when started with n-dimensional array of cells in nonquiescent state, the special cell reaches a final state. In this paper, we propose a homogeneous systolic automaton with n-dimensional layers (n-HSPA), and investigate some properties of real-time n-HSPA. Specifically, we first investigate a relationship between the accepting powers of real-time n-HSPA’s and real-time 1-nCA’s. We next show the recognizability of n-dimensional connected tapes by real-time n-HSPA’s.

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
203 - 206
Publication Date
2014/12/15
ISSN (Online)
2352-6386
ISSN (Print)
2405-9021
DOI
10.2991/jrnal.2014.1.3.7How 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  - Homogeneous Systolic Pyramid Automata with n-Dimensional Layers
JO  - Journal of Robotics, Networking and Artificial Life
SP  - 203
EP  - 206
VL  - 1
IS  - 3
SN  - 2352-6386
UR  - https://doi.org/10.2991/jrnal.2014.1.3.7
DO  - 10.2991/jrnal.2014.1.3.7
ID  - Sakamoto2014
ER  -