Volume 1, Issue 3, December 2014, Pages 203 - 206
Homogeneous Systolic Pyramid Automata with n-Dimensional Layers
Makoto Sakamoto, Makoto Nagatomo, Tatsuma Kurogi, Satoshi Ikeda, Masahiro Yokomichi, Hiroshi Furutani, Takao Ito, Yasuo Uchida, Tsunehiro Yoshinaga
Available Online 15 December 2014.
- https://doi.org/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.
- Open Access
- This is an open access article distributed under the CC BY-NC license.
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 - https://doi.org/10.2991/jrnal.2014.1.3.7 ID - Sakamoto2014 ER -