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.7
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/).