表題番号:2016K-100 日付:2017/02/19
研究課題オートマタ理論に基づく生体科学反応系の構成的解析
研究者所属(当時) 資格 氏名
(代表者) 教育・総合科学学術院 教育学部 教授 横森 貴
研究成果概要

化学反応オートマトン(CRA: Chemical Reaction Automaton)とは自然計算モデルのひとつであり化学反応系に基づく計算システムである.この計算モデルにおいて,状態遷移が一意にきまる決定性モデルの計算能力について以下の結果を得た.

(1). 決定性CRAの逐次的適用による計算能力は,ペトリネットの計算能力よりも真に劣る.

(2). 空入力モードを許す決定性CRAの計算能力は決定性CRAの計算能力以下である.

以上により,CRAによる決定性の計算能力の計算量理論における位置づけが解明され,化学反応による決定性計算の理論的な限界に関する知見が得られた.