Homogeneous Systolic Pyramid Automata with n-Dimensional Layers

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)

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  -