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

化学反応オートマトン(CRA: Chemical Reaction Automaton)とは自然計算モデルのひとつであり化学反応系に基づく計算システムである.CRAにおいて計算過程が一意的に後戻り可能な計算だけを許すモデルを可逆的とよぶ.本研究では,この可逆的CRAに関する計算能力について考察し,以下の結果を得た.

(1). 空入力モードを許す可逆的CRAの計算能力はペトリネットの計算能力より真に劣る.

(2). 可逆的CRAの計算能力は正規言語のクラスと比較不可能な位置づけにある.

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