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

化学反应自动机分析及应用研究

基本信息

批准号：
13J03528
负责人：
大久保文哉
金额：
$ 1.02万
依托单位：
Waseda University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2013
资助国家：
日本
起止时间：
2013 至 2015-03-31
项目状态：
已结题

项目摘要

化学反応オートマトン(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に採録された。さらに、これらの結果をまとめ、早稲田大学に博士論文として提出した。

反应自动机（RA）是通过Okubo，Yokomori和Kobayashi在2012年提出的多个集合重写生化反应的计算模型。在这里，每个反应由代表反应物，抑制剂和产物的多个组组定义。此外，RA通过提供输入符号字符串而定义为字符串的接收器。这允许通过将其与常规计算模型进行比较，以计算反应系统的信息处理能力进行分析。今年，除了传统的最大平行RA（坡道）外，我们还使用顺序应用分析了RA（RASQ）的计算能力，例如“仅在一步中仅应用一个反应”。此时，允许空字符（λ输入模式）和不允许不允许的情况（正常模式）作为输入方法的情况。我们将这些不同RA的计算能力与图灵机（TMS）的计算能力进行了比较，这是传统计算理论和乔姆斯基层次结构的基础。结果，结果表明，λ输入模式的RASQ具有多功能的图灵计算，但是在正常模式下RASQ的计算能力确实不如TM。该结果与坡道在两种输入模式中具有图灵计算的多功能性相反。此外，像RAMP一样，RASQ还引入了限制该区域计算复杂性的类，并分析了它们的计算能力并将其与其他计算模型进行了比较。获得的结果是在国际学术杂志Rairo理论信息学和应用中收集的。此外，这些结果被汇编并作为博士论文提交给Waseda大学。