Four-Dimensional Homogeneous Systolic Pyramid Automata
-
- Nagatomo Makoto
- Faculty of Engineering, University of Miyazaki
-
- Sakamoto Makoto
- Faculty of Engineering, University of Miyazaki
-
- Sun Chongyang
- Faculty of Engineering, University of Miyazaki
-
- Yano Shinnosuke
- Faculty of Engineering, University of Miyazaki
-
- Ikeda Satoshi
- Faculty of Engineering, University of Miyazaki
-
- Ito Takao
- Institute of Engineering, Hiroshima University
-
- Ito Tsutomu
- Institute of Engineering, Hiroshima University
-
- Uchida Yasuo
- Department of Business Administration, Ube National College of Technology
-
- Yoshinaga Tsunehiro
- Department of Computer Science & Electronic Engineering, National Institute of Technology
説明
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 fourdimensional 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 four-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. 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 four-dimensional tape in time a-1. Moreover, a 1- way four-dimensional 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 four-dimensional array of cells in nonquiescent state, the special cell reaches a final state. In this paper, we propose a homogeneous systolic automaton with four-dimensional layers (4-HSPA), and investigate some properties of real-time 4-HSPA. Specifically, we first investigate a relationship between the accepting powers of realtime 4-HSPA's and real-time 1-4CA's. We next show the recognizability of four-dimensional connected tapes by real-time 4-HSPA's
収録刊行物
-
- 人工生命とロボットに関する国際会議予稿集
-
人工生命とロボットに関する国際会議予稿集 22 670-674, 2017-01-19
株式会社ALife Robotics
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390564238096991744
-
- ISSN
- 21887829
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- OpenAIRE
-
- 抄録ライセンスフラグ
- 使用不可