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