離散時間論理型有限力学系モデル（DT-BFDS）は、力学系モデル（dynamical systems）に離散時間で動作する、頂点が一定でその状態が論理値であるという制限を加えて、単純化したものである。DT-BFDSは離散時間で変化する社会現象、あるいはタンパク質間や遺伝子間の相互作用ネットワークのシミュレーションの道具として使われており、また、DT-BFDSの性質に関する問題が計算量理論を用いて研究されている。DT-BFDSは従来決定性のモデルであり、非決定的な動きをするモデルの体系はまだ確立されていない。確率的なモデルを使用したDT-BFDSモデルが幾つか提案されているが、そこに於ける確率的選択の使用は、初期値の生成など、動作の一部に限られている。

 

本研究の目的は、このDT-BFDSに不確定要素を導入する方法を提案し、それによって生じるモデルの計算力を調べる事である。ここでは二つの独立した方式を不確定性の導入方を提案する。その一つは、状態の更新に使われる関数に、頂点毎に選択肢を与える事であり、もう一つは、頂点が各時刻において順々に状態の更新を行うと仮定し、その順序に選択肢を与える事である。この二つの方式をそれぞれ何種類かに分け、それらを組み合わせる事により、多岐のモデルが定義できる。本講演では、この試みの初期の結果を発表する。まず、モデルの多項式時間埋め込み可能性の概念を定義し、このようなモデルの相互関係を立証する。さらには、いくつかのモデルの計算能力を到達可能性問題の計算量理論的分析により、明らかにする。