著者

奥田 剛 井上 克司 井上敦之 伊藤暁

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.110, pp.17-24, 2005-11-11

---

Pシステムは、生物学上の特徴をもつセルを用いた並列計算モデルであり,本論文ではこのモデルを利用した1つの触手をもつ通信機能のあるPシステムを取り上げる.これをCommunicating P System with One Tentacle (1CPST)と呼ぶ.研究では、次の結果を示す.意の有限オートマトンMが与えられたとき Mが受理する言語L(M)を受理するような1CPSTを構成する方法.T ={0}なる入力テープ集合は深さ2の1CPSTでは受理できるが 深さ1の1CPSTでは受理できない.意の正則表現が与えられたとき その正則表現を表す言語を直接受理するような深さ2の1CPSTを構成する方法.P system is a parallel computing model that uses the cell having the biological feature. This paper investigates the P system that has the communicating function with one tentacle, called Communicating P System with One Tentacle (1CPST). In this study, the following results are obtained. A method of constructing a 1CPST that accepts the same language as that of arbitrary finite automaton. It is impossible for 1CPST's of depth 1 to accept the set T = {0}, which can be accepted by a 1CPST of depth 2. A method of constructing a 1CPST of depth 2 that directly accepts the languages expressed by arbitrary regular expressions.