化学反応オートマトンの解析と応用に関する研究

点击翻译按钮获取中文摘要

化学反応オートマトン(Reaction Automaton : RA)は、大久保・横森・小林によって2012年に提案された、多重集合書き換えによる生体化学反応の計算モデルである。ここで各反応は反応物、抑制物、生成物をあらわす多重集合の三つ組みによって定義される。また、RAは入力記号列を外部から与えることにより、文字列の受理器として定義されている。これにより、従来の計算モデルと比較をおこなうことで、反応系のもつ情報処理能力を計算理論的に解析することができる。本年度は、従来の極大並列的(maximally parallel)によるRA (RAmp)に加え、「1ステップで1つの反応のみを適用する」ような逐次的適用を用いたRA (RAsq)の計算能力に関して、計算能力の解析をおこなった。このとき、入力の方法として空文字を許す場合(λ入力モード)と、許さない場合(通常モード)を考慮した。これらの種々のRAの計算能力と、従来の計算理論の基となるチューリング機械(TM)の計算能力やチョムスキー階層との比較をおこなった。結果として、λ入力モードにおけるRAsqはTuring計算万能性を有するが、通常モードにおけるRAsqの計算能力はTMに真に劣ることが示された。この結果は、RAmpがどちらの入力モードにおいてもTuring計算万能性を有することと対照的な結果である。さらに、RAmpと同様に、RAsqについても領域計算量を制限したクラスを導入し、その計算能力の解析や他の計算モデルとの比較をおこなった。得られた結果は、国際学術雑誌であるRAIRO Theoretical Informatics and Applicationsに採録された。さらに、これらの結果をまとめ、早稲田大学に博士論文として提出した。