ハイブリッド・セル・オートマトンを用いた生物系と化学系の解析と検証

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

昨年度より、グラフ書き換え系、特にグラフの構造が変化せず、各々のノードの状態だけが変化するシステムを、時相論理を用いて解析する方法に関する研究を進めている。このようなシステムには、いわゆるセル・オートマトンも含まれる。昨年度は、時相論理を用いてセル・オートマトンを解析する方法を定式化し、実際に一次元のセル・オートマトンや分散アルゴリズムの解析を試みた。今年度は、以上の方法を発展させるために、以下の二つの方向の研究を進めた。一つは、二次元のセル・オートマトンの解析を行うために、上下左右の4方向の様相を持つ時相論理である4CTL (computation tree logic)の定式化とその充足可能性判定方法を開発した。4CTLの充足可能性判定は決定不能であるため、Presburger算術を用いた近似的な判定方法を定式化した。そして、二次元のセル・オートマトンの例として、分子コンピューティングにおけるタイリングの解析を行った。もう一つは、セル・オートマトンのハイブリッド化と、その解析方法に関する研究を行った。セル・オートマトンのハイブリッド化とは、各セルに時間とともに変化する連続パラメータを導入することを意味する。解析のための時相論理の方も、連続パラメータに対処するために拡張しなければならない。本研究では、時相論理を包含する論理として、ガード付きフラグメント(guarded fragment)とその充足可能性判定に関する研究を進めた。また、ハイブリッド化されたセル・オートマトンの例として、簡単なニューラル・ネットワークの解析を行った。