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.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 ALife Robotics Corp. Ltd.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).