有限モデルのCTL・LTL検証

有限Kripke構造の分岐時間CTL・線形時間LTLの性質を無限実行経路の意味論で検証する。

無限実行を対象とするモデル検査です。有限回の試行だけで将来の性質が成立したとは判定しません。

項目を入力・選択してから「計算する」を押してください。

選択内容に応じて、残りの入力項目を案内します。

計算する内容
状態と成立する命題ラベル必須
行状態ID真となる命題(カンマ・空白区切り) 任意操作
1
2

2列を左端の欄へタブ区切りで貼り付けられます。1000行まで。

例:状態s0にpとreadyが成立するなら「p, ready」。指定しない命題はその状態で偽です。

有向遷移任意
行遷移元の状態ID遷移先の状態ID操作
1
2

2列を左端の欄へタブ区切りで貼り付けられます。1000行まで。

各行が1本の有向遷移です。自己ループも入力できます。

初期状態必須
行初期状態のID操作
1

1列を左端の欄へタブ区切りで貼り付けられます。1000行まで。

複数の初期状態を指定できます。すべての初期状態で式を評価します。

公正条件(任意)任意
行無限回成立すべき命題名操作
1

1列を左端の欄へタブ区切りで貼り付けられます。16行まで。

各ラベルが実行経路で無限回真になるjustice条件。空欄なら公正制約なし。

CTL/LTLは無限経路を前提とするため、遷移関係を全域にします。

CTL: AG p、AF p、E[p U q]。LTL: G p、F p、G(req -> F ack)、p U q。!・&・|・->・括弧が使えます。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

CTLの存在Uは μZ.(ψ∧Fair ∨ (φ∧EX Z))、EGはφに限定した公正SCCへ到達できる状態集合。AX/AF/AG/AUは公平な存在経路の双対で計算します。LTLは否定式をNNFへ変換し、Uの無限延期を排除する一般化Büchi受理集合とjustice条件を満たす積グラフのサイクルを探索します。経路は状態0からの無限系列、Xは次状態、Fは現在以降のどこか、Gは現在以降のすべて、Uは右側の成立まで左側が成立する強until、Rはその双対です。

初期状態に対する性質の真偽、到達/公正継続可能状態数、CTL状態判定、対応可能な反例のlasso。

計算例(架空の数値)

状態s0(pなし)からs0への自己ループを持ち、初期状態がs0ならAG pもAF pも偽です。G pとF pも偽で、反例はs0を無限反復するループです。

適用対象と限界

状態1~1000、入力遷移1000行以内、1状態最大32命題、公正条件16件以内の有限モデル。過去時間演算子、CTL*、強公正(compassion)、遷移の無限分岐、任意のSMVファイル解析、外部定理証明器は対象外です。LTLの積状態12,000・積辺48,000・操作500,000の上限超過は未判定です。。

採用した方式

  • CTL 公正固定点評価(E2137-v1.0):対象範囲 EX AX EF AF EG AG E[U] A[U]と論理結合/適用地域 global
  • LTL 一般化Büchi受理サイクル検出(E2137-v1.0):対象範囲 X F G U Rと命題論理、全初期状態・公正無限経路/適用地域 global

方法と出典

方法:E2137 CTL justice fixpoint / LTL generalized-Büchi tableau v1.0 (2026-11-15)。データ記録日:2026-11-15。