Four-Dimensional Homogeneous Systolic Pyramid Automata

Authors

  • Makoto Nagatomo Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan.
  • Makoto Sakamoto Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan.
  • Chongyang Sun Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan.
  • Shinnosuke Yano Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan.
  • Satoshi Ikeda Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan.
  • Takao Ito Institute of Engineering, Hiroshima University, Higashi-Hiroshima, Hiroshima 739-8527, Japan.
  • Tsutomu Ito Institute of Engineering, Hiroshima University, Higashi-Hiroshima, Hiroshima 739-8527, Japan.
  • Yasuo Uchida Department of Business Administration, Ube National College of Technology, Ube, Yamaguchi 755-8555, Japan.
  • Tsunehiro Yoshinaga Department of Computer Science and Electronic Engineering, Tokuyama college of Technology, Shunan, Yamaguchi 745-8585, Japan.

Keywords:

Cellular Automaton, Diameter, Finite Automaton, Four-Dimension, Parallelism, Pattern Recognition, Real Time,

Abstract

Cellular automaton is famous as a kind of the parallel automaton. 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 four-dimensional layers (4-HSPA) is a pyramid stack of four-dimensional arrays of cells in which the bottom four-dimensional layer (level 0) has size an (a≥1), the next lowest 4(a-1), and so forth, the (a-1)st fourdimensional 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. A 4-HSPA is said to be a real-time 4-HSPA if for every four-dimensional tape of size 4a (a≥1), it accepts the fourdimensional tape in time a-1. Moreover, a 1- way fourdimensional cellular automaton (1-4CA) can be considered as a natural extension of the 1-way two-dimensional cellular automaton to four-dimension. The initial configuration is accepted if the last special cell reaches a final state. A 1-4CA is said to be a real- time 1-4CA if when started with fourdimensional array of cells in nonquiescent state, the special cell reaches a final state. In this paper, we proposed a homogeneous systolic automaton with four-dimensional layers (4-HSPA), and investigated some properties of real-time 4-HSPA. Specifically, we first investigated the relationship between the accepting powers of real-time 4-HSPA’s and real-time 1-4CA’s. We next showed the recognizability of four-dimensional connected tapes by real-time 4-HSPA’s.

Downloads

Published

2017-06-01

How to Cite

Nagatomo, M., Sakamoto, M., Sun, C., Yano, S., Ikeda, S., Ito, T., Ito, T., Uchida, Y., & Yoshinaga, T. (2017). Four-Dimensional Homogeneous Systolic Pyramid Automata. Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 9(2-5), 75–77. Retrieved from https://jtec.utem.edu.my/jtec/article/view/2397