時相論理(temporal logic)とは、命題論理に「次に」「いつか」「ずっと」「〜まで」の演算子を加え、状態が移り変わる系の性質を述べる論理である。実行の列の上で語る線形時間の LTL と、分岐する未来の上で「ある経路で」「すべての経路で」と語る CTL が代表で、表現力は互いに比較できない。有限の Kripke 構造の上での真偽の判定(モデル検査)は、CTL では論理式と構造の大きさの積の時間で解ける。LTL では論理式を Büchi 型の自動機械に翻訳して解け、PSPACE 完全である。
時相論理(temporal logic)は、命題論理 に「次に」「いつか」「ずっと」「〜まで」にあたる演算子を加えて、時間とともに変わる系の性質を述べる論理である。「2 つの工程が同時に危険区域に入ることはない」「要求はいつか応えられる」のような主張を、状態の列についての論理式として書ける。PnueliPnu77 がプログラムの検証に持ち込んだ。
時間の見方は 2 つある。1 本の実行の列の上で語る 線形時間 の LTL と、分岐する未来の木の上で「ある未来では」「どの未来でも」と語る 分岐時間 の CTL である。この記事では両者を定義し、3 つのことを証明する。第 1 に両者の表現力は比較できない。第 2 に CTL のモデル検査は論理式と構造の大きさの積の時間でできる。第 3 に LTL のモデル検査は Büchi 型の自動機械への翻訳で解け、PSPACE 完全である。
$\mathrm{AP}$ を原子命題の有限集合とする。
Kripke 構造 とは、有限集合 $S$、全域な関係 $R\subset S\times S$(どの $s$ にも $(s,t)\in R$ となる $t$ がある)、ラベル $L\colon S\to2^{\mathrm{AP}}$ の組 $M=(S,R,L)$ である。$s$ からの 経路 とは、$\pi_0=s$、$(\pi_i,\pi_{i+1})\in R$ を満たす無限列 $\pi=\pi_0\pi_1\cdots$ である。その 語 は $L(\pi):=L(\pi_0)L(\pi_1)\cdots\in(2^{\mathrm{AP}})^\omega$ である。大きさは $|M|:=|S|+|R|$ とする。
状態は系のある瞬間、$R$ は 1 歩の遷移、$L$ はその瞬間に成り立つ命題である。これは 様相論理 の Kripke モデルと同じ形で、関係を「次の時刻」と読む。全域性は、すべての実行が無限に続くと考えるための約束である。
線形時相論理(linear temporal logic、LTL)の論理式を
$$\varphi::=p\mid\lnot\varphi\mid\varphi\land\varphi\mid\mathsf X\varphi\mid\varphi\,\mathsf U\,\varphi\qquad(p\in\mathrm{AP})$$
で定める。語 $\sigma=\sigma_0\sigma_1\cdots\in(2^{\mathrm{AP}})^\omega$ と、その接尾辞 $\sigma^i:=\sigma_i\sigma_{i+1}\cdots$ について、$\sigma\models p\iff p\in\sigma_0$、$\sigma\models\mathsf X\varphi\iff\sigma^1\models\varphi$ とし、
$$\sigma\models\varphi\,\mathsf U\,\psi\iff\text{ある }j\ge0\text{ で }\sigma^j\models\psi\text{ かつ、すべての }i< j\text{ で }\sigma^i\models\varphi$$
とする($\lnot,\land$ は通常どおり)。略記 $\top:=p\lor\lnot p$、$\mathsf F\varphi:=\top\,\mathsf U\,\varphi$(いつか)、$\mathsf G\varphi:=\lnot\mathsf F\lnot\varphi$(ずっと)を使う。構造については、$M,s\models\varphi$ を「$s$ からの すべての 経路 $\pi$ で $L(\pi)\models\varphi$」と定める。
計算木論理(computation tree logic、CTL)の論理式を
$$\varphi::=p\mid\lnot\varphi\mid\varphi\land\varphi\mid\mathsf{EX}\varphi\mid\mathsf E[\varphi\,\mathsf U\,\varphi]\mid\mathsf{EG}\varphi$$
で定める。状態 $s$ で真偽が決まり、$M,s\models\mathsf{EX}\varphi$ は「$s$ からのある経路 $\pi$ で $M,\pi_1\models\varphi$」、$\mathsf E[\varphi\,\mathsf U\,\psi]$ は「ある経路 $\pi$ と $j\ge0$ で $M,\pi_j\models\psi$、$i< j$ で $M,\pi_i\models\varphi$」、$\mathsf{EG}\varphi$ は「ある経路 $\pi$ のすべての $i$ で $M,\pi_i\models\varphi$」とする。略記 $\mathsf{EF}\varphi:=\mathsf E[\top\,\mathsf U\,\varphi]$、$\mathsf{AX}\varphi:=\lnot\mathsf{EX}\lnot\varphi$、$\mathsf{AF}\varphi:=\lnot\mathsf{EG}\lnot\varphi$、$\mathsf{AG}\varphi:=\lnot\mathsf{EF}\lnot\varphi$ を使う。
CTL では経路の量化 $\mathsf{E},\mathsf{A}$ と時間の演算子が必ず対になる。LTL では全体の前に暗黙の $\mathsf A$ が 1 つだけ付く。両方を自由に混ぜた論理が CTL$^*$ で、EH86 が導入した。
2 つの工程がそれぞれ $n$(待機外)→ $t$(順番待ち)→ $c$(危険区域)→ $n$ と進むとする。状態は組 $(\ell_1,\ell_2)\ne(c,c)$ で、1 歩ごとにどちらか一方が進み、相手が $c$ の間は $t$ から $c$ へ進めない。8 状態、14 遷移の構造になる。命題 $c_1$ は「工程 1 が $c$ にいる」を表し、他も同様とする。始点 $(n,n)$ での真偽は次のとおりである。
| 性質 | 論理式 | 真偽 |
|---|---|---|
| 安全性(LTL) | $\mathsf G\lnot(c_1\land c_2)$ | 真 |
| 安全性(CTL) | $\mathsf{AG}\lnot(c_1\land c_2)$ | 真 |
| 応答(LTL) | $\mathsf G(t_1\to\mathsf Fc_1)$ | 偽 |
| 応答(CTL) | $\mathsf{AG}(t_1\to\mathsf{AF}c_1)$ | 偽 |
| 応答の可能性 | $\mathsf{AG}(t_1\to\mathsf{EF}c_1)$ | 真 |
| いつでも初期に戻れる | $\mathsf{AG}\,\mathsf{EF}(n_1\land n_2)$ | 真 |
応答が偽になるのは、工程 1 を $t$ で待たせたまま工程 2 だけが回り続ける経路があるからである。公平な実行に限って調べたいなら、「無限回〜ならば」の形の仮定 $\mathsf G\mathsf F\alpha\to\cdots$ を付ければよく、これは LTL で書ける。
演算子の基本の法則として、$\mathsf F\varphi\equiv\varphi\lor\mathsf{XF}\varphi$、$\mathsf G\varphi\equiv\varphi\land\mathsf{XG}\varphi$、$\varphi\,\mathsf U\,\psi\equiv\psi\lor(\varphi\land\mathsf X(\varphi\,\mathsf U\,\psi))$ がある。定義から $j=0$ か否かで分ければよい。$\mathsf U$ はこの再帰の式だけでは決まらない。$\psi$ がいつまでも成り立たずに $\varphi$ だけが続く語は、式の右辺を満たし続けるからである。この「最小の解」を選ぶ必要が、次の不動点と、後の自動機械の受理条件に現れる。
モデル検査(model checking)とは、$M,s,\varphi$ が与えられたとき $M,s\models\varphi$ かを判定する問題である。$X\subset S$ について $\mathrm{pre}(X):=\{s\mid\text{ある }t\in X\text{ で }(s,t)\in R\}$ とする。
$\varphi,\psi$ の真である状態の集合を $A,B$ とする。$\mathsf E[\varphi\,\mathsf U\,\psi]$ の真である状態の集合は $Z\mapsto B\cup(A\cap\mathrm{pre}(Z))$ の 最小 不動点であり、$\mathsf{EG}\varphi$ の真である状態の集合は $Z\mapsto A\cap\mathrm{pre}(Z)$ の 最大 不動点である。
最小性は証人の長さについての帰納法、最大性は不動点の中に無限の経路を作ることで示す。
$\mathsf E[\varphi\,\mathsf U\,\psi]$ の集合 $E$ は、定義を $j=0$ か否かで分ければ不動点である。$Z$ を任意の不動点とすると、証人の長さ $j$ についての帰納法で $E\subset Z$ である($j=0$ なら $B\subset Z$、$j>0$ なら $s\in A$ で次の状態が短い証人をもつので $s\in A\cap\mathrm{pre}(Z)\subset Z$)。
$\mathsf{EG}\varphi$ の集合 $G$ も定義から不動点である。$Z$ を $Z\subset A\cap\mathrm{pre}(Z)$ を満たす集合(とくに不動点)とする。$s\in Z$ なら $s\in A$ で、$Z$ の中に後続があるので、これを繰り返して $Z$ の中の無限の経路を作れる。その各点は $A$ に属するので $s\in G$ である。$\square$
$\varphi$ の真である状態の集合は、時間 $O(|\varphi|\cdot|M|)$ で計算できる。
部分論理式を短い順に処理し、それぞれが真である状態の集合を求める。部分論理式は高々 $|\varphi|$ 個なので、各演算を $O(|M|)$ でできればよい。$\lnot,\land$ は明らかで、$\mathsf{EX}$ は辺を 1 回なめればよい。
$\mathsf E[\varphi\,\mathsf U\,\psi]$ は、prop-tl-fix の最小不動点を $B$ から逆向きの探索で求める。$A$ の中だけを通って $B$ に到達できる状態が答えで、各辺を高々 1 回たどる。
$\mathsf{EG}\varphi$ を求める。$A$ の上の誘導部分グラフ $M_A$ を作り、その 強連結成分 を線形時間で求める。成分が 非自明 とは、2 点以上からなるか、自己ループをもつ 1 点であることをいう。求める集合は、$M_A$ の中で非自明な成分へ到達できる状態の全体 $T$ である。実際、$T$ の点からは非自明な成分まで進んだあと、その中を回り続ける無限の経路があり、全部 $A$ の中にある。逆に $s\in G$ なら、$A$ の中の無限の経路は $S$ の有限性からある状態を 2 度以上通る。無限回通る点の全体は互いに行き来できるので同じ非自明な成分に入り、$s$ はそこへ到達できる。逆向きの探索は $O(|M|)$ である。$\square$
この算法の形は Clarke–Emerson–SistlaCES86 による。
LTL の論理式 $\varphi$ と CTL の論理式 $\psi$ が 同値 であるとは、すべての Kripke 構造 $M$ と状態 $s$ で $M,s\models\varphi\iff M,s\models\psi$ となることをいう。
1 の証明は短い。LTL は「すべての経路」についての主張なので、経路を減らしても真のままである。
$M$ を状態 $s_0,s_1$、辺 $s_0\to s_0$、$s_0\to s_1$、$s_1\to s_1$、$L(s_1)=\{p\}$、$L(s_0)=\emptyset$ とする。$M'$ を $s_0$ と自己ループだけの部分構造とする。$M,s_0$ で $\mathsf{EF}p$ も $\mathsf{AG}\,\mathsf{EF}p$ も真であり、$M',s_0$ ではどちらも偽である。一方、$M',s_0$ の唯一の経路は $M,s_0$ の経路でもあるから、LTL の論理式 $\varphi$ について $M,s_0\models\varphi$ ならば $M',s_0\models\varphi$ である。よって同値な $\varphi$ はない。$\square$
2 は、CTL の論理式が有限の深さしか見られないことを使う。次の はしご を作る。
$n\ge1$ について $M_n$ を、状態 $a_0,\dots,a_n,b_1,\dots,b_n$、$L(a_i)=\{p\}$、$L(b_i)=\emptyset$、辺 $a_i\to a_i$、$a_i\to b_i$($i\ge1$)、$b_i\to a_{i-1}$ の構造とする。$M'_n$ は $M_n$ に最上段の戻る辺 $b_n\to a_n$ を足した構造とする。
$M_n$ では番号が増えないので、$b$ を通るのは有限回で、どの経路もいつか $a_i$ に留まる。よって $M_n,a_n\models\mathsf{FG}p$ である。$M'_n$ では $(a_nb_n)^\omega$ が経路なので $M'_n,a_n\not\models\mathsf{FG}p$ である。CTL の論理式の 深さ $d(\psi)$ を、$\mathsf{EX},\mathsf E[\cdot\,\mathsf U\,\cdot],\mathsf{EG}$ の入れ子の数とする。
$\psi$ を深さ $d$ の CTL の論理式とする。真偽 $\alpha,\beta$ があって、$i\ge2d$ の $a_i$ で $\psi$ の真偽は $\alpha$、$i\ge2d+1$ の $b_i$ で $\beta$ である($M_n$ の $n$ によらない)。さらに $n\ge2d+1$ なら、$M'_n$ の $a_n$ でも $\alpha$、$b_n$ でも $\beta$ である。
$\psi$ の構造についての帰納法で、$\mathsf{EX},\mathsf E[\cdot\,\mathsf U\,\cdot],\mathsf{EG}$ の値を一段ごとに比べる。
$a_i,b_i$ からは番号 $i$ 以下の状態にしか行けないので、$M_n$ での真偽は $n$ によらず、$M'_n$ の $i< n$ の状態でも同じである。$\psi$ についての帰納法で示す。$p$ と $\lnot,\land$ は明らかである。$\chi,\chi_1,\chi_2$ を深さ $\le d-1$ とし、$N:=2(d-1)$ とする。部分論理式は $a_i$($i\ge N$)と $b_i$($i\ge N+1$)で定数になっている。
$M_n$ の側: $\mathsf{EX}\chi$ は、$a_i$ の後続が $a_i,b_i$、$b_i$ の後続が $a_{i-1}$ なので定数である。$\mathsf E[\chi_1\mathsf U\chi_2]$ を $a_i$($i\ge N+1$)で見る。$a_i$ か $b_i$ で $\chi_2$ が真の場合と、$\chi_1$ が途中で偽になる場合は、$i$ によらず真偽が決まる。残るのは $a,b$ の両方で $\chi_1$ が真、$\chi_2$ が偽の場合で、このとき $a_i$ の真偽は $b_i$ を経て $a_{i-1}$ の真偽に等しく、やはり定数である。$b_i$ の真偽は $\chi_2,\chi_1$ の値と $a_{i-1}$ の真偽で決まるので、$i\ge N+2=2d$ で定数である。$\mathsf{EG}\chi$ は、$a_i$ では自己ループがあるので $\chi$ の値そのもの、$b_i$ では $\chi$ の値と $a_{i-1}$ の真偽で決まる。
$M'_n$ の側($n\ge2d+1$): 異なるのは $b_n$ の後続 $a_n$ が増えることだけである。帰納法の仮定から、部分論理式の値は最上段でも $M_n$ と同じである。$\mathsf{EX}\chi$ では、$b_n$ の後続 $a_n,a_{n-1}$ の値はどちらも $a$ の定数値で、$M_n$ と同じになる。$\mathsf E[\chi_1\mathsf U\chi_2]$ が $a_n$ で真である有限の証人の経路をとり、$a_n$ を最後に通った所から先だけを残すと、戻る辺を使わないので $M_n$ の経路になる。逆に $M_n$ の経路は $M'_n$ の経路だから、$a_n$ で真偽は $M_n$ と同じである。$\mathsf{EG}\chi$ は $a_n$ で $\chi$ の値そのものなので同じである。$b_n$ ではどちらも、$\chi$ たちの値と後続 $a_n,a_{n-1}$ の真偽で決まり、後者は $a$ の定数値である。$\square$
CTL の論理式 $\psi$ が $\mathsf{FG}p$ と同値だとして、$d:=d(\psi)$、$n:=2d+1$ とする。lem-tl-ladder から $M_n,a_n$ と $M'_n,a_n$ で $\psi$ の真偽は等しい。しかし $\mathsf{FG}p$ の真偽は異なる。これは矛盾である。$\square$
$\mathsf{EF}p$ の主張は Emerson–HalpernEH86 の Theorem 3 に、$\mathsf{FG}p$ の主張はその双対の形で同 Theorem 7 にある(同論文の枠組みの構造について述べられている)。上のはしごの証明は、有限の Kripke 構造の上で独自に組み立てたものである。
「$\mathsf{FG}p$ を CTL に直すなら $\mathsf{AF}\,\mathsf{AG}p$」と考えたくなるが、これは同値でない。状態 $0,1,2$、辺 $0\to0$、$0\to1$、$1\to2$、$2\to2$、$L(0)=L(2)=\{p\}$、$L(1)=\emptyset$ を考える。状態 $0$ からのどの経路も、$0$ に留まるか $2$ に留まるので $\mathsf{FG}p$ は真である。一方、経路 $0^\omega$ の上のどの点でも、「次に $1$ へ行ける」ので $\mathsf{AG}p$ は偽であり、$\mathsf{AF}\,\mathsf{AG}p$ は偽である。LTL の主張は経路が決まってから語るが、CTL の $\mathsf{AG}$ はその時点で分岐の全部を見る。
LTL のモデル検査は、論理式を無限語の自動機械に翻訳して解くVar96。有限オートマトン を無限語に広げたものである。
一般化 Büchi 自動機械 は、有限の状態集合 $Q$、初期状態の集合 $Q_0$、遷移の関係 $\Delta\subset Q\times Q$、ラベル $\lambda\colon Q\to\Sigma$、受理の族 $F_1,\dots,F_k\subset Q$ の組である。語 $\sigma\in\Sigma^\omega$ の 走り は、$q_0\in Q_0$、$(q_i,q_{i+1})\in\Delta$、$\lambda(q_i)=\sigma_i$ を満たす無限列で、すべての $l$ で $F_l$ の状態を無限回通るとき受理する。$k=1$ の場合が Büchi 自動機械 である。
$\mathsf{cl}(\varphi)$ を $\varphi$ の部分論理式とその否定の全体($\lnot\lnot\psi$ は $\psi$ と同一視)とする。$B\subset\mathsf{cl}(\varphi)$ が 整合的 であるとは、各 $\psi\in\mathsf{cl}(\varphi)$ で $\psi,\lnot\psi$ のちょうど一方を含み、$\psi_1\land\psi_2\in B\iff\psi_1,\psi_2\in B$ で、$\psi_1\,\mathsf U\,\psi_2\in\mathsf{cl}(\varphi)$ について「$\psi_2\in B$ なら $\psi_1\,\mathsf U\,\psi_2\in B$」「$\psi_1\,\mathsf U\,\psi_2\in B$、$\psi_2\notin B$ なら $\psi_1\in B$」を満たすことをいう。語 $\sigma$ に対し、$\sigma$ の接尾辞の上で真な論理式を集めた $\{\psi\mid\sigma^i\models\psi\}$ は整合的である。
$A_\varphi$ の状態を整合的な集合 $B$ とし、$Q_0:=\{B\mid\varphi\in B\}$、$\lambda(B):=B\cap\mathrm{AP}$ とする。$(B,B')\in\Delta$ は、$\mathsf X\psi\in\mathsf{cl}(\varphi)$ で $\mathsf X\psi\in B\iff\psi\in B'$、かつ $\psi_1\,\mathsf U\,\psi_2\in\mathsf{cl}(\varphi)$ で
$$\psi_1\,\mathsf U\,\psi_2\in B\iff\psi_2\in B\text{ または }(\psi_1\in B\text{ かつ }\psi_1\,\mathsf U\,\psi_2\in B')$$
を満たすこととする。$\varphi$ の $\mathsf U$ の部分論理式ごとに、$F_{\psi_1\mathsf U\psi_2}:=\{B\mid\psi_1\,\mathsf U\,\psi_2\notin B\text{ または }\psi_2\in B\}$ を受理の族とする。
ここでの $\mathrm{AP}$ は $\varphi$ に現れる命題とする。状態の数は高々 $2^{|\varphi|}$ である。
$A_\varphi$ が受理する語の全体は、$\varphi$ を満たす語の全体に等しい。
満たす語は受理される。 $\sigma\models\varphi$ なら $B_i:=\{\psi\in\mathsf{cl}(\varphi)\mid\sigma^i\models\psi\}$ が走りになる。遷移の条件は $\mathsf X,\mathsf U$ の定義と $\mathsf U$ の再帰の式である。どの $i$ でも、$\psi_1\mathsf U\psi_2\notin B_i$ であるか、$\sigma^i\models\psi_1\mathsf U\psi_2$ の証人 $j\ge i$ で $\psi_2\in B_j$ となるので、$F_{\psi_1\mathsf U\psi_2}$ の状態は $i$ 以降に必ず現れる。
受理されれば満たす。 $B_0B_1\cdots$ を $\sigma$ の受理する走りとする。すべての $i$ と $\psi\in\mathsf{cl}(\varphi)$ で $\psi\in B_i\iff\sigma^i\models\psi$ を $\psi$ の構造についての帰納法で示す。$p$ は $\lambda$ の条件から、$\lnot,\land$ は整合性から、$\mathsf X$ は遷移の条件から従う。$\psi=\psi_1\mathsf U\psi_2$ とする。
$\sigma^i\models\psi$ のとき、証人 $j$ をとる。帰納法の仮定から $\psi_2\in B_j$ で、整合性から $\psi\in B_j$ である。$i\le k< j$ の $k$ で $\psi_1\in B_k$ なので、遷移の条件で $k=j-1,\dots,i$ と逆にたどり $\psi\in B_i$ を得る。
$\psi\in B_i$ のとき、$\psi_2\in B_j$ となる最初の $j\ge i$ があることを示す。なければ遷移の条件から、すべての $j\ge i$ で $\psi\in B_j$、$\psi_2\notin B_j$ となり、$B_j\notin F_\psi$ が $j\ge i$ で続いて受理の条件に反する。この $j$ までの $k< j$ では、整合性から $\psi_1\in B_k$ である。帰納法の仮定から $\sigma^i\models\psi$ である。$\square$
受理の族が $\mathsf U$ の「最小の解」を選ぶ役をしている。受理条件を除くと、$\mathsf Fp$ の機械は $p$ が一度も成り立たない語でも $\mathsf Fp\in B_i$ のまま走れてしまう。翻訳はVar96 Corollary 23 の主張の形(Büchi 自動機械で状態数 $2^{O(|\varphi|)}$)に対応する。同論文は交代自動機械を経由するが、上は論理式の整合的な集合を状態にする直接の構成である。一般化の受理は、$1,\dots,k$ を数えるカウンタを状態に足せば Büchi に直る。
LTL のモデル検査は PSPACE 完全である。時間 $|M|\cdot2^{O(|\varphi|)}$ で解ける。
上界。 $M,s\not\models\varphi$ は、$s$ からの経路の語で $\lnot\varphi$ を満たすものがあることと同値である。thm-tl-gba から、$M$ と $A_{\lnot\varphi}$ の積のグラフ(頂点は $(t,B,l)$、$l$ はカウンタで、$\varphi$ の命題に制限した $L(t)$ と $\lambda(B)$ の一致を要求する)に、初期点から到達でき自分へ戻る受理の頂点があることと同値である。実際、そのような投げ縄は受理する経路を与え、逆に受理する無限の走りの中で、有限のグラフの受理の頂点が 2 度現れる。頂点の数は $|S|\cdot2^{O(|\varphi|)}$ で、全体を作って探せば時間の上界を得る。空間については、頂点を 1 つずつ記憶して非決定的に投げ縄を当てれば多項式の空間で足り、Savitch の定理(計算量理論)で決定的にできる。補集合をとっても PSPACE は変わらない。
下界。 $L$ を PSPACE の言語とし、$T$ を $L$ を判定する 1 テープの決定性の機械で、入力 $w$ に対し高々 $m=m(|w|)$ マス(多項式)を使うものとする。受理・拒否の状態に入ったら様相を変えないように改める。様相を長さ $m$ の文字列とし、$\#$ で区切って並べる。文字の集合 $\Delta$ は $\#$、テープ文字、(状態、テープ文字)の組である。$T$ は決定性で局所的なので、ある位置の次の様相での文字は、前の様相の連続 3 文字で決まる。その関数を $f$ とする(Cook–Levinの定理 の表と同じである)。
$\Delta$ の各文字を命題 $p_\delta$ とし、$K$ を $\Delta$ の完全有向グラフ(自己ループつき、$L(\delta)=\{p_\delta\}$)とする。$\psi_w$ を次の連言とする。
PSPACE 完全性は Sistla–ClarkeSC85 の結果である(Var96 Theorem 24、25)。LTL の 充足可能性 も PSPACE 完全である。上界は、充足可能性が $A_\varphi$ の受理する語の存在と同値で、上と同じ投げ縄の探索が多項式の空間でできることから従う。下界は、$\psi_w$ に「各時刻で $p_\delta$ がちょうど 1 つ真である」を表す $\mathsf G$ の式を足せばよい。Var96 Theorem 25 は、固定した論理式について構造の大きさに関する複雑さが NLOGSPACE 完全であることも述べている。
「偶数番目の位置ではつねに $p$」という語の性質は、Büchi 自動機械で受理できるが、LTL では書けない。
自動機械は位置の偶奇と文字を状態に記憶すればよい($\mathrm{AP}=\{p\}$ なら def-tl-gba の形で 3 状態)。LTL については、$w_i:=p^i\,\emptyset\,p^\omega$ を考えると、入れ子の数が $k$ の論理式の真偽は $i>k$ で一定になる。一方、性質は $i$ の偶奇で真偽が変わる。
LTL については、$w_i:=p^i\,\emptyset\,p^\omega$($i$ 個の $\{p\}$ のあとに $\emptyset$、その後は $\{p\}$)を考える。$\mathsf{X,U}$ の入れ子の数が $k$ の論理式の真偽は、$i>k$ の $w_i$ で一定であることを、$k$ の帰納法で示す。$\mathsf X\psi$ は $w_{i-1}$ を見るだけである。$\psi_1\mathsf U\psi_2$ を $w_i$($i>k$)で見ると、$w_i,w_{i-1},\dots,w_k$ の上では $\psi_1,\psi_2$ の値は定数である。$\psi_2$ が真なら全体も真、$\psi_1,\psi_2$ が偽なら全体も偽で、$\psi_1$ が真で $\psi_2$ が偽なら全体の真偽は $w_k$ での真偽に等しい。いずれも $i$ によらない。性質は $i$ が奇数のとき成り立ち、偶数のとき成り立たないので、書けない。$\square$
LTL を自動機械と同じ表現力まで広げる試みに WolperWol83 がある。
| 外す条件・変えること | 反例 | 成り立たなくなること |
|---|---|---|
| $R$ の全域性 | 後続のない状態 $s$ | $\mathsf{AX}\varphi\to\mathsf{EX}\varphi$ |
| 経路が 1 本であること | 下の分岐 $B$ | $M,s\models\varphi$ か $M,s\models\lnot\varphi$ の二者択一 |
| $\mathsf{FG}$ を $\mathsf{AF}\,\mathsf{AG}$ に | ex-tl-fgaf の構造 | $\mathsf{FG}p\Rightarrow\mathsf{AF}\,\mathsf{AG}p$ |
| 最小不動点 | $p$ が偽の自己ループ 1 点 | prop-tl-fix の $\mathsf{EF}p$ の特徴づけ(最大不動点では不可) |
| $A_\varphi$ の受理の族 | $\mathsf Fp$ と語 $\emptyset^\omega$ | thm-tl-gba |
| はしごの段数 $n\ge2d+1$ | $n=1$ と下の深さ 3 の $\psi$ | lem-tl-ladder の一致 |
全域性。 後続がなければ $\mathsf{AX}\lnot\top$ は真で、$\mathsf{EX}\top$ は偽である。
分岐。 $B$ を状態 $0,1,2$、辺 $0\to1$、$0\to2$、$1\to1$、$2\to2$、$L(1)=\{p\}$、他は空とする。$\mathsf Xp$ は経路 $02^\omega$ で偽、$\lnot\mathsf Xp$ は経路 $01^\omega$ で偽なので、$0$ でどちらも成り立たない。LTL の否定は語の上の否定で、「全経路で」の外には出ない。
不動点。 $p$ が偽の状態 $s$ と自己ループだけなら、$p$ の真である集合は空なので、$Z=\{s\}$ も $Z=\emptyset$ も $Z\mapsto\mathrm{pre}(Z)$ の不動点で、$\mathsf{EF}p$ の真の集合は最小の $\emptyset$ である。
受理の族。 $\mathsf Fp$ の機械の状態 $\{\mathsf Fp\}$($p\notin$)は自分へ遷移でき、受理の族がなければ $\emptyset^\omega$ を受理する。しかし $\emptyset^\omega\not\models\mathsf Fp$ である。
はしごの深さ。 補題は $n$ の下限を要する。実際 $\psi:=\mathsf{EF}(\lnot p\land\mathsf{AX}\,\mathsf{AG}p)$ は、$b_1$ の後続が $a_0$ だけである $M_1$ では $a_1$ で真だが、$M'_1$ では $b_1$ が $a_1$ へ戻れるので偽である。$\psi$ の深さは $3$ で、$n=1$ は $2d+1$ に足りない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する