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

使用混合元胞自动机分析和验证生物和化学系统

基本信息

批准号：
14658088
负责人：
萩谷昌己
金额：
$ 1.47万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Exploratory Research
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2006
项目状态：
已结题

项目摘要

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

自去年以来，我们一直在研究分析图形重写系统的方法，尤其是图形结构不变，并且仅使用时间逻辑更改的系统。这样的系统还包括所谓的单元自动机。去年，我们制定了一种使用时间逻辑来分析细胞自动机的方法，并实际试图分析一维细胞自动机和分布式算法。今年，我们在两个方向上进行了研究，以开发上述方法：一种是分析二维细胞自动机，我们开发了4CTL（计算树逻辑）的公式，这是一种具有四个方向上，向下，向下，左和右的时间相逻辑，并确定其令人满意的潜力。由于无法确定4CTL令人满意的概率确定，因此已经制定了使用Presburger算术的近似判断方法。然后，作为二维细胞自动机的一个示例，进行了分子计算中的平铺分析。另一个是研究细胞自动机及其分析方法的研究。细胞自动机的杂交意味着将随时间变化的连续参数引入每个单元格。还必须扩展用于分析的时间逻辑以解决连续参数。在这项研究中，我们对守卫碎片及其令人满意的潜力进行了研究，作为涉及时间逻辑的逻辑。另外，进行了简单的神经网络分析作为杂交细胞自动机的示例。