表題番号：2013B-063 日付：2014/05/20
研究課題反応オートマトンによる化学反応系の解析
研究者所属（当時） 資格 氏名
（代表者） 教育・総合科学学術院 教授 横森　貴
（連携研究者） 大学院教育学研究科 日本学術振興会博士研究員DC2 大久保文哉
研究成果概要
申請者らはここ数年来，化学反応系をモデル化した計算システムの理論的解析を行っている．
一般に，化学反応は反応分子(R), 抑制分子(I), 生成分子(P)の３つが関わるとして抽象化
し，これを多重集合の３つ組a=(R,I,P)で定式化した．この３つ組による反応を適用すると，
『いま考えている分子の溶液（多重集合）TがRを含みIを含まないとき，この反応によりT
からRが消費され，同時にPが新たに生成される』と解釈される．このとき反応aによりTから
新たにT'(=T-R+P)が生成される．
　このような反応aをすべて可能な限り適用するような反応の多重集合をαしたとき，αを
極大並列適用とよび，このときの変化を T⇒α T' と表す．このような形式化において，
外部からの入力をも受け取りつつ，内部状態が遷移するオートマトンを反応オートマトン
(RA: Reaction Automata)として定義した．
　本研究では主に，反応規則の適用モードを「（極大並列ではなく）逐次的適用（すなわち，
上記のαが１つの反応aの場合）」に焦点をあて，そのときの反応オートマトンの生成能力に
ついて考察を行った．すなわち，外部入力列a1,...,anがRA:Mによって受理されるとは，指定
された状態の多重集合T0から，指定された最終状態の多重集合Fへ至る遷移の系列：
T0⇒a1 T1⇒a2 T2 ⇒・・・⇒an Tn⇒・・・⇒Fが存在するときと定義する（ただし，ここでは
各遷移における逐次的に適用される反応規則は省略されている）．そして，このように受理
される入力列全体からなる集合L(M)をMによって受理される言語とよび，その数学的性質
（計算量）を理論的に解析した．
　RAは化学反応系をモデル化した記号列受理器であり，（従来型のオートマトンと異なり）
試験管内や細胞内の環境を想定した“多重集合(multiset)”を扱う計算モデルという特徴がある．
得られた結果は以下の通りである．
　入力のサイズnをパラメタとしたとき，計算に用いる多重集合のサイズが関数s(n)以下である
ように制限されたRAをs(n)-限定RAとよぶ．このとき，
(i) 言語Lがあるs(n)-限定RAによって受理される必要十分条件は，Lがlog s(n)限定のTuring
　　Machine (TM)で受理されることである．また，
(ⅱ) s(n)が指数関数であるようなs(n)-限定RAによって受理される集合の族は，文脈依存言語族
　　CSLに一致する，ことが示された．

さらに，s(n)-制限というTMの部分クラスを新たに考案し，その計算能力を探究した．このs(n)-
制限TM:Mとは，「サイズnの入力を受理するならば，入力途中で読まれた接頭辞の長さをd(とき，Mは利用できる多重集合のサイズはs(d)を超えない」という条件を満たすときをいう．このとき，
以下の結果が得られた：
(ⅲ) 任意のRAによって受理される言語はs(n)-制限TMによって受理される．
(ⅳ）特に，線形領域限定RAで受理される言語はlog n-制限のlog n領域限定TMによって受理される．
(ⅴ)　任意の帰納的可算言語はRAで受理される言語の準同型写像によって表される．（文献[1])

これらの結果は，化学反応による計算能力を，従来から研究されているTMによる計算量のクラスとの
比較において解明している点で重要であり，新たな知見を与える．

さらに，これまでに得られたRAに関する一連の研究成果をサーベイ論文として，国際会議IWNC2013
において発表した(文献[2])．