权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
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に採録された。さらに、これらの結果をまとめ、早稲田大学に博士論文として提出した。

Chemical Reaction Automaton (RA), Okubo, Yokomori, Kobayashi, 2012 Proposal, Multiple Set Text, Calculation of Biological Chemical Reaction The definition of three groups of reaction, inhibitor and product is given. For example, if you want to use a text string, you can use it as an input string. The information processing ability of the computer system is analyzed by the computer theory. This year, RA (RAmp) will be added to the maximum parallel, and the calculation capacity of RA (RAsq) will be analyzed. The method of entry and exit shall be considered in the case where the text is allowed (λ entry and exit) and in the case where the text is allowed (usually exit). A comparison of computational power levels of mechanical (TM) systems. The results show that RAsq has the ability to compute omnipotence, and RAsq has the ability to compute omnipotence. The result is that RAMP has no entry force, and the result is that RAMP has no entry force, and the result is that RAMP has no entry force. RMP and RASq are used to limit the amount of computation in the domain, analyze the computational power and compare the computational power. RAIRO Theoretical Informatics and Applications The results of this research are presented in the dissertation of Waseda University.