Büchi自動機械

同義語:BüchiオートマトンBüchi automaton

概要

Büchi自動機械(Büchi automaton)とは、無限語を読む非決定性の有限オートマトンで、受理状態を無限回通る走りがあるときに入力を受理するものである。認識できる言語はちょうど ω 正規言語で、空かどうかは状態のグラフの探索で判定でき、空でなければ周期的な語を含む。決定性のものでは認識できない言語があるが、非決定性のものは Ramsey の定理による色の分解で補集合をとる操作で閉じている。これを使うと自然数の上の単項二階論理 S1S の決定可能性が示せる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 有限オートマトン, 正規言語

Büchi自動機械(Büchi automaton、Büchiオートマトン)は、無限に続く文字列(無限語)を読む非決定性の 有限オートマトン で、受理状態を無限回通る走りがあるときに入力を受理するものである。J. R. Büchi が、自然数の順序の上の単項二階論理 S1S が決定可能であることを示すために導入した(LS18 §1)。時相論理 の線形時相論理の検証でも、仕様とプログラムの振る舞いをこの自動機械に直して扱う。
この記事では、Büchi自動機械が認識する言語がちょうど ω正規言語であること(thm-bu-omega-regular)、空かどうかを判定でき、空でなければ周期的な語を含むこと(thm-bu-empty)、決定性のものでは足りないこと(thm-bu-nondet)を示す。主定理は補集合で閉じていること(thm-bu-complement)で、Ramseyの定理 を使って証明する。最後にこれらを合わせて S1S の決定可能性を導く。
以下、$\Sigma$ は空でない有限集合(アルファベット)、$\Sigma^*$ は有限語の全体、$\Sigma^+$ は空でない有限語の全体、$\Sigma^\omega$ は無限語 $w=a_0a_1a_2\cdots$($a_i\in\Sigma$)の全体である。$U\subset\Sigma^*$、$V\subset\Sigma^+$ について、$UV^\omega$ は $uv_1v_2v_3\cdots$($u\in U$、$v_i\in V$)の形の無限語の全体を表す。

定義

Büchi自動機械

Büchi自動機械 $\mathcal A=(Q,\Sigma,\delta,I,F)$ は、有限集合 $Q$(状態の集合)、遷移の集合 $\delta\subset Q\times\Sigma\times Q$、初期状態の集合 $I\subset Q$、受理状態の集合 $F\subset Q$ からなる。無限語 $w=a_0a_1\cdots$ の上の 走り とは、$q_0\in I$ で、すべての $i$ について $(q_i,a_i,q_{i+1})\in\delta$ となる状態の列 $r=q_0q_1q_2\cdots$ のことである。$r$ に無限回現れる状態の集合を $\mathrm{Inf}(r)$ と書き、$\mathrm{Inf}(r)\cap F\ne\emptyset$ のとき $r$ は 受理的 であるという。受理的な走りをもつ無限語の全体を $L(\mathcal A)$ と書き、$\mathcal A$ が 認識する言語 という。$I$ が $1$ 元で、各 $(q,a)$ について $(q,a,q')\in\delta$ となる $q'$ がちょうど $1$ つあるとき、$\mathcal A$ は 決定性 であるという。

定義は Var96 の Büchi 自動機械の定義と LS18 §6 による。有限語 $u=a_0\cdots a_{n-1}$ と状態 $p,q$ について、$p=s_0,s_1,\dots,s_n=q$ で $(s_i,a_i,s_{i+1})\in\delta$ となる状態の列($u$ を読む $p$ から $q$ への道)があることを $p\xrightarrow{u}q$ と書く。そのような道で $s_0,\dots,s_n$ のどれかが $F$ に入るものがあることを $p\xrightarrow[F]{u}q$ と書く。

ω正規言語

$L\subset\Sigma^\omega$ が ω正規 であるとは、有限個の 正規言語 $U_1,\dots,U_k\subset\Sigma^*$ と $V_1,\dots,V_k\subset\Sigma^+$ があって
$$ L=\bigcup_{i=1}^kU_iV_i^{\omega} $$
となることをいう。

例

1 が無限回現れる語

$\Sigma=\{0,1\}$、$Q=\{q_0,q_1\}$、$I=\{q_0\}$、$F=\{q_1\}$ とし、文字 $a$ を読むとどの状態からも $q_a$ へ移る決定性の自動機械を考える。走りは $q_0$ のあとに読んだ文字をなぞるので、受理的であることは $1$ が無限回現れることと同値である。この言語は $(0^*1)^\omega$ で、ω正規である。

0 が有限回しか現れない語

$Q=\{p,q\}$、$I=\{p\}$、$F=\{q\}$ とし、遷移を $(p,0,p)$、$(p,1,p)$、$(p,1,q)$、$(q,1,q)$ とする。走りは $p$ にしばらくとどまり、ある時点で $q$ へ移ると以後は $1$ しか読めない。受理的な走りは必ず $q$ へ移るので、$L(\mathcal A)=\{0,1\}^*1^\omega$ は「$0$ が有限回しか現れない語」の全体である。$q$ へ移る時点を「最後の $0$ のあと」と推測する非決定性が欠かせないことを thm-bu-nondet で示す。

要求と応答

「要求 $r$ が出るたびに、同時かそれ以後に応答 $g$ が来る」という性質を考える。文字は $\{r,g\}$ の部分集合で、$Q=\{q_0,q_1\}$、$I=F=\{q_0\}$ とする。文字 $a$ を読むとき、$g\in a$ なら $q_0$ へ、$r\in a$ かつ $g\notin a$ なら $q_1$ へ移り、どちらでもなければ状態を保つ。$q_1$ は「答えの来ていない要求がある」ことを表す。ある要求に応答が来なければ、その時点から先はずっと $q_1$ にとどまる。すべての要求に応答が来れば、$q_1$ に入るたびに後で $g$ を読んで $q_0$ へ戻る。よってこの決定性の自動機械が性質をちょうど認識する。

和と共通部分

和と共通部分で閉じていること

$\mathcal A_1,\mathcal A_2$ を Büchi自動機械とする。$L(\mathcal A_1)\cup L(\mathcal A_2)$ と $L(\mathcal A_1)\cap L(\mathcal A_2)$ はどちらも Büchi自動機械で認識できる(Var96 Proposition 5、6)。

和は、状態の集合を交わらないようにして $Q_1\sqcup Q_2$ とし、遷移・初期状態・受理状態もそれぞれ和をとった自動機械で認識される。
共通部分を考える。$\mathcal A_k=(Q_k,\Sigma,\delta_k,I_k,F_k)$ とし、状態の集合を $Q_1\times Q_2\times\{1,2\}$ とする。第 3 成分の 旗 は、どちらの受理状態を待っているかを表す。$(p,q,i)$ から文字 $a$ で $(p',q',j)$ へ移れるのは、$(p,a,p')\in\delta_1$、$(q,a,q')\in\delta_2$ で、$j$ が次の規則で決まるときとする。

  • $i=1$ かつ $p\in F_1$ なら $j=2$。
  • $i=2$ かつ $q\in F_2$ なら $j=1$。
  • それ以外なら $j=i$。
    初期状態を $I_1\times I_2\times\{1\}$、受理状態を $F_1\times Q_2\times\{1\}$ とする。
    この自動機械の走りは、第 1・第 2 成分がそれぞれ $\mathcal A_1,\mathcal A_2$ の走りで、旗はそれらから一意に決まる。走りが受理的なら $F_1\times Q_2\times\{1\}$ を無限回通り、そのたびに旗は $2$ になる。旗が $1$ に戻るのは第 2 成分が $F_2$ に入ったときだけなので、第 1 成分は $F_1$ を、第 2 成分は $F_2$ を無限回通る。
    逆に $\mathcal A_1,\mathcal A_2$ の受理的な走り $r_1,r_2$ をとり、旗をつけた走りを考える。ある時点から旗が $1$ のままなら、その後 $r_1$ が $F_1$ を通った時点で旗が $2$ になり矛盾する。$2$ のままの場合も同様である。よって旗は無限回 $1$ から $2$ に変わり、変わる直前の状態は $F_1\times Q_2\times\{1\}$ に入る。$\square$

ω正規言語との一致

Büchi自動機械と ω正規言語

$L\subset\Sigma^\omega$ について、次は同値である。

  1. ある Büchi自動機械 $\mathcal A$ について $L=L(\mathcal A)$。
  2. $L$ は ω正規である。
    さらに 1 のとき、$p\xrightarrow{u}q$ となる $u$ の全体を $U_{p,q}$、$q\xrightarrow{v}q$ となる $v\in\Sigma^+$ の全体を $V_q$ とすると、$L(\mathcal A)=\bigcup_{p\in I,\,q\in F}U_{p,q}V_q^{\omega}$ である。

要点:受理状態を無限回通る位置で走りを切る。逆向きは、$V$ の自動機械の初めと終わりを新しい状態でつなぐ。

詳しい証明を開く

1 から 2。$U_{p,q}$ は、$\mathcal A$ の遷移を使い、初期状態を $p$、受理状態を $q$ とする非決定性の有限オートマトンが受理する言語なので、Kleeneの定理(正規言語) により正規である。$V_q=U_{q,q}\cap\Sigma^+$ も正規である。受理的な走り $r=q_0q_1\cdots$ では、$F$ が有限なので、ある $q\in F$ が無限回現れる。その位置を $n_0< n_1< \cdots$ とし、$w$ を位置 $n_0$ までの部分 $u$ と、$n_{k-1}$ から $n_k$ までの部分 $v_k$ に切ると、$u\in U_{q_0,q}$、$v_k\in V_q$ である。逆に $w=uv_1v_2\cdots$($u\in U_{p,q}$、$v_k\in V_q$、$p\in I$)なら、それぞれの道をつないだ走りは $q$ を無限回通る。これで等式と 2 が示された。

2 から 1。prop-bu-boolean により、正規な $U\subset\Sigma^*$、$V\subset\Sigma^+$ について $UV^\omega$ が認識できればよい。$V$ を受理する非決定性の有限オートマトン $(P,\Sigma,\eta,J,G)$ をとり、新しい状態 $s$ を加える。遷移は $\eta$ に、$(j,a,x)\in\eta$($j\in J$)のとき $(s,a,x)$、$(y,a,g)\in\eta$($g\in G$)のとき $(y,a,s)$、$(j,a,g)\in\eta$($j\in J$、$g\in G$)のとき $(s,a,s)$ を加える。初期状態と受理状態をともに $\{s\}$ とする。$s$ を出て途中で $s$ を通らずに $s$ へ戻る道が読む語は、ちょうど $V$ の元である($1$ 文字なら $(s,a,s)$、$2$ 文字以上なら最初と最後の遷移を $J$、$G$ の側に付け替える)。よってこの自動機械は $V^\omega$ を認識する。次に $U$ を受理する非決定性の有限オートマトン $(R,\Sigma,\theta,K,H)$ を交わらないように並べ、$(y,a,h)\in\theta$($h\in H$)のとき $(y,a,s)$ を加え、初期状態を $K$($\varepsilon\in U$ なら $K\cup\{s\}$)とする。$R$ へ戻る遷移はないので、受理的な走りは $R$ の中で $U$ の語を読んで $s$ へ移り、以後 $V^\omega$ の走りになる。これは $UV^\omega$ を認識する。$\square$

thm-bu-omega-regular の後半から、空かどうかの判定が得られる。

空性の判定と周期的な語

$L(\mathcal A)\ne\emptyset$ であることと、$p\in I$、$q\in F$、$u\in\Sigma^*$、$v\in\Sigma^+$ で $p\xrightarrow{u}q$ かつ $q\xrightarrow{v}q$ となるものがあることは同値である。このとき $uv^\omega\in L(\mathcal A)$ である。とくに、空でない $L(\mathcal A)$ は 周期的な語($uv^\omega$ の形の語)を含み、$L(\mathcal A)$ が空かどうかは状態の有向グラフの到達可能性を調べて判定できる。

thm-bu-omega-regular の等式から、$L(\mathcal A)\ne\emptyset$ であることは、ある $p\in I$、$q\in F$ について $U_{p,q}$ と $V_q$ が空でないことと同値である。$u\in U_{p,q}$、$v\in V_q$ をとると、$u$ の道のあとに $v$ の道を繰り返してつないだ走りは $q$ を無限回通るので、$uv^\omega\in L(\mathcal A)$ である。条件は、状態を頂点、遷移を辺とする有向グラフで「$I$ から到達できる $q\in F$ で、長さ $1$ 以上の閉路に乗るものがある」ことと同じで、有限の探索で確かめられる。$\square$

この判定は線形時間ででき、問題は NLOGSPACE 完全である(Var96 Proposition 13。この記事では証明しない)。

決定性では足りないこと

決定性の Büchi自動機械の限界

$\{0,1\}^*1^\omega$ を認識する決定性の Büchi自動機械はない(Var96 Proposition 8)。

決定性の $\mathcal A$ が $\{0,1\}^*1^\omega$ を認識したとする。決定性なので各無限語の走りはただ $1$ つで、有限語 $x$ を読んだあとの状態 $\delta(x)$ が決まる。$1^\omega\in L(\mathcal A)$ なので、ある $n_1\ge1$ で $\delta(1^{n_1})\in F$ である。次に $1^{n_1}01^\omega\in L(\mathcal A)$ なので、ある $n_2\ge1$ で $\delta(1^{n_1}01^{n_2})\in F$ である。これを繰り返して $n_1,n_2,\dots$ を選び、$w=1^{n_1}01^{n_2}01^{n_3}0\cdots$ とおく。$w$ の走りは各接頭辞 $1^{n_1}0\cdots01^{n_k}$ を読んだ時点で $F$ に入るので受理的である。ところが $w$ には $0$ が無限回現れ、$w\notin\{0,1\}^*1^\omega$ である。$\square$

補集合 $(1^*0)^\omega$($0$ が無限回現れる語)は、ex-bu-inf の $0$ と $1$ を入れ替えた決定性の自動機械で認識できる。よって決定性の Büchi自動機械が認識する言語の族は補集合で閉じていない。それでも、非決定性まで許せば補集合で閉じていることを次の節で示す。

補集合定理

有限語の自動機械では、部分集合構成で決定性にしてから受理状態を入れ替えれば補集合が得られる。無限語ではこの方法が使えない(thm-bu-nondet)。代わりに、有限語を「自動機械の上でのふるまい」で有限個の類に分け、無限語をその類の語の無限の積に分解する。
色 を定める。$u\in\Sigma^+$ について
$$ R_u=\{(p,q)\mid p\xrightarrow{u}q\},\qquad R^F_u=\{(p,q)\mid p\xrightarrow[F]{u}q\} $$
とし、組 $c(u)=(R_u,R^F_u)$ を $u$ の色という。色は $Q\times Q$ の部分集合の組なので、$n=\lvert Q\rvert$ として高々 $2^{2n^2}$ 通りである。色 $c$ をもつ語の全体を $[c]$ と書く。

色の積

関係の合成を $\circ$ と書き($(p,q)\in R\circ S$ は、ある $m$ で $(p,m)\in R$、$(m,q)\in S$ となること)、色の積を $(R,R')\cdot(S,S')=(R\circ S,\ R\circ S'\cup R'\circ S)$ と定める。このとき $c(uv)=c(u)\cdot c(v)$ で、各 $[c]$ は正規言語である。

$uv$ を読む道は、$u$ を読み終えた時点の状態 $m$ で $2$ つの道に分かれ、$F$ を通る位置は前半か後半にある($m$ 自身は両方に数える)。これが積の式である。積は結合的で、$c(ua)=c(u)\cdot c(a)$($a\in\Sigma$)だから、色の全体と開始状態を状態とし、色に文字の色を右から掛けていく決定性の有限オートマトンが $[c]$ を受理する。$\square$

色が同じ語への置き換え

色 $c,d$ について $K_{c,d}=[c][d]^\omega$ とおく。$K_{c,d}\subset L(\mathcal A)$ と $K_{c,d}\cap L(\mathcal A)=\emptyset$ のどちらかが成り立つ。

$w=uv_1v_2\cdots\in K_{c,d}\cap L(\mathcal A)$ と $w'=u'v'_1v'_2\cdots\in K_{c,d}$ をとる($u,u'\in[c]$、$v_k,v'_k\in[d]$)。$w$ の受理的な走りを、各区切りの位置での状態 $s_0,s_1,\dots$($s_0$ は $u$ を読んだあと、$s_k$ は $v_k$ を読んだあと)で見る。初期状態 $q_0$ について $(q_0,s_0)\in R_u$、$(s_{k-1},s_k)\in R_{v_k}$ で、走りが $F$ を無限回通るので、無限個の $k$ で $(s_{k-1},s_k)\in R^F_{v_k}$ である。色が等しいので、同じ対は $R_{u'}$、$R_{v'_k}$、$R^F_{v'_k}$ にも入る。それぞれの対を実現する $u'$、$v'_k$ の道をつなげば、$w'$ の走りで $F$ を無限回通るものができる。よって $w'\in L(\mathcal A)$ である。$\square$

無限語の分解

すべての $w\in\Sigma^\omega$ について、$w\in K_{c,d}$ となる色 $c,d$ がある。

$w=a_0a_1\cdots$ とし、$i< j$ について $2$ 元集合 $\{i,j\}$ を色 $c(a_i\cdots a_{j-1})$ で塗る。色は有限個なので、無限版の Ramseyの定理 により、無限集合 $\{n_0< n_1< \cdots\}$ で、その $2$ 元部分集合がすべて同じ色 $d$ になるものがある。$n_0\ge1$ としてよい。$u=a_0\cdots a_{n_0-1}$、$v_k=a_{n_{k-1}}\cdots a_{n_k-1}$ とおけば、$c(v_k)=d$ で、$c=c(u)$ について $w\in K_{c,d}$ である。$\square$

Büchi の補集合定理

Büchi自動機械 $\mathcal A$ について、$\Sigma^\omega\setminus L(\mathcal A)$ を認識する Büchi自動機械がある。状態の数は $2^{O(n^2)}$ にとれる($n=\lvert Q\rvert$)。

$\mathcal C$ を、$K_{c,d}\cap L(\mathcal A)=\emptyset$ となる色の組 $(c,d)$ の全体とし、
$$ \Sigma^\omega\setminus L(\mathcal A)=\bigcup_{(c,d)\in\mathcal C}K_{c,d} $$
を示す。右辺が左辺に含まれるのは $\mathcal C$ の定め方による。逆に $w\notin L(\mathcal A)$ とする。lem-bu-ramsey により $w\in K_{c,d}$ となる $c,d$ がある。lem-bu-saturation により $K_{c,d}$ は $L(\mathcal A)$ に含まれるか交わらないかのどちらかで、$w$ は $L(\mathcal A)$ に入らないので交わらない。よって $(c,d)\in\mathcal C$ である。
色は有限個なので右辺は有限個の和である。lem-bu-color により $[c]$、$[d]$ は正規で、$[d]\subset\Sigma^+$ だから、右辺は ω正規である。thm-bu-omega-regular により Büchi自動機械で認識できる。
状態の数を見る。$[c]$ を受理する lem-bu-color のオートマトンは $2^{2n^2}+1$ 個の状態をもち、組 $(c,d)$ は $2^{4n^2}$ 個以下である。thm-bu-omega-regular の構成は状態を $1$ 個足すだけなので、合計は $2^{O(n^2)}$ である。$\square$

$(c,d)\in\mathcal C$ かどうかも判定できる。$[c]$ か $[d]$ が空なら $K_{c,d}=\emptyset$ で $(c,d)\in\mathcal C$ であり、空かどうかは lem-bu-color のオートマトンで分かる。lem-bu-saturation の証明と同じく、$[c]$、$[d]$ が空でないとき、$K_{c,d}$ が $L(\mathcal A)$ に交わることは、$Q$ を頂点とし $R_d$ を辺、$R^F_d$ を印の付いた辺とするグラフで、$I$ から $R_c$ の $1$ 歩で行ける頂点から、印の付いた辺を無限回通る道が出ることと同値で、thm-bu-empty と同じ探索で調べられる。よって補集合の自動機械は実際に構成できる。この証明の方針は LS18 §8(Fact 8.1〜8.9、Theorem 8.10)と同じである。Büchi のもとの構成の大きさは二重指数で、上の $2^{O(n^2)}$ の上界は Sistla・Vardi・Wolper による(Var96 Proposition 7 のあとの説明)。

周期的な語で決まること

ω正規言語 $L_1,L_2$ について、$L_1=L_2$ であることと、両者が同じ周期的な語を含むことは同値である。また $L_1\subset L_2$ かどうかは判定できる。

$L_1\setminus L_2=L_1\cap(\Sigma^\omega\setminus L_2)$ は prop-bu-boolean と thm-bu-complement により Büchi自動機械で認識できる。これが空でなければ thm-bu-empty により周期的な語を含む。$L_2\setminus L_1$ も同様である。包含の判定は、この自動機械に thm-bu-empty の判定を使えばよい。$\square$

決定化と計算量

Rabin 自動機械 は、受理条件を状態の集合の組の有限族 $(L_1,U_1),\dots,(L_k,U_k)$ に替えたもので、ある $i$ について $L_i$ を無限回、$U_i$ を有限回だけ通る走りを受理的とする。次の結果はこの記事では証明しない。

  • McNaughton の定理:Büchi自動機械は、同じ言語を認識する決定性の Rabin 自動機械に直せる(Var96 Proposition 10)。逆に Rabin 自動機械は Büchi自動機械に直せる(同 Proposition 9)。
  • Safra の構成は $n$ 状態の Büchi自動機械から $2^{O(n\log n)}$ 状態、$O(n)$ 組の決定性の Rabin 自動機械を作る。これを使った補集合の構成も $2^{O(n\log n)}$ 状態で、Michel の下界によりこれは本質的に改善できない(Var96 Proposition 10 のあとの説明)。有限語の自動機械の補集合が $2^n$ 状態でできるのと比べ、指数の肩が非線形になる。
  • $L(\mathcal A)=\Sigma^\omega$ かどうかの判定は PSPACE 完全である(Var96 Proposition 14)。

S1S の決定可能性

S1S は自然数の順序 $(\mathbb N,<)$ の上の単項二階論理である。自然数を動く変数 $x,y,\dots$ と自然数の集合を動く変数 $X,Y,\dots$ をもち、原子論理式は $x< y$ と $x\in X$、論理結合子と両方の変数の量化で論理式を作る。自由変数が集合変数 $X_1,\dots,X_k$ だけの論理式 $\varphi$ の解釈は無限語で表せる。$\Sigma=\{0,1\}^k$ とし、$w$ の位置 $n$ の文字の第 $i$ 成分が $1$ であることを $n\in X_i$ と読む。

Büchi の定理

S1S の論理式 $\varphi(X_1,\dots,X_k)$ ごとに、$\varphi$ を満たす解釈を表す無限語の全体を認識する Büchi自動機械がある。とくに、S1S の閉論理式が $(\mathbb N,<)$ で真かどうかは判定できる(LS18 Fact 5.2、Theorem 9.1、Theorem 10.2)。

要点:論理式の構成に沿って自動機械を作る。否定に thm-bu-complement、存在量化に非決定性を使う。

詳しい証明を開く

自然数の変数 $x$ は「ちょうど $1$ 元の集合」を表す集合変数に置き換えられ、$x< y$ は「$X$ の元より $Y$ の元が大きい」、$x\in Z$ は $X\subset Z$ になる(LS18 §10、Fact 10.1)。「$1$ 元である」も下の原子論理式から書ける。よって原子論理式 $X\subset Y$ と $X\lhd Y$($m\in X$、$n\in Y$、$m< n$ となる $m,n$ がある)、$\land$、$\lnot$、$\exists X$ だけで作った論理式を扱えばよい(同 §4)。

$X\subset Y$ は、該当する $2$ 成分が $(1,0)$ である文字を読めない $1$ 状態の自動機械(その状態が初期かつ受理)で認識される。$X\lhd Y$ は状態 $0,1,2$ で、$0,1,2$ はどの文字でも自分に留まれ、$X$ 成分が $1$ の文字で $0\to1$、$Y$ 成分が $1$ の文字で $1\to2$ へ移れ、初期状態 $0$、受理状態 $2$ の自動機械で認識される。$\land$ は prop-bu-boolean、$\lnot$ は thm-bu-complement による。$\exists X_{k+1}\varphi$ は、$\varphi$ の自動機械の遷移 $(p,(b,e),q)$($b\in\{0,1\}^k$、$e\in\{0,1\}$)を $(p,b,q)$ に替えた自動機械で認識される。走りが $e$ を推測して $X_{k+1}$ を選ぶからである。閉論理式では $k=0$ で、$\Sigma$ は $1$ 文字なので、真であることは自動機械が空でないことと同値であり、thm-bu-empty で判定できる。$\square$

$(\mathbb N,<)$ の一階の論理式は S1S の論理式でもあるので、$(\mathbb N,<)$ の一階の理論も決定可能である。論理式を自動機械の演算に翻訳するこの方法は、時相論理 などほかの論理にもそのまま働く(LS18 §1)。

反例の表

外す条件反例成り立たなくなること
thm-bu-complement の非決定性(決定性に限る)$(1^*0)^\omega$補集合も同じ種類の自動機械で認識できること
def-bu-omega-regular の $V_i\subset\Sigma^+$$V=\{\varepsilon\}$$UV^\omega$ が無限語の集合であること
thm-bu-empty の $v\in\Sigma^+$遷移のない $1$ 状態の自動機械条件が空でないことと同値であること
prf-bu-boolean の旗(受理状態を $F_1\times F_2$ にする)$1$ 文字の上で $2$ 状態を交互に通る自動機械 $2$ つ共通部分を認識すること
lem-bu-saturation の色の $R^F_u$$b$ で状態が入れ替わる自動機械と $aa$、$bb$色が同じ語に置き換えても受理が変わらないこと
lem-bu-ramsey の色が有限個であること語の長さを色とする塗り分け同じ色の無限集合がとれること
表の確かめ

1 行目:$(1^*0)^\omega$ は決定性で認識できるが、補集合 $\{0,1\}^*1^\omega$ は thm-bu-nondet により決定性では認識できない。
2 行目:$u\varepsilon\varepsilon\cdots=u$ は有限語である。
3 行目:状態 $q$ を初期かつ受理とし遷移をなくすと、走りがないので言語は空だが、$u=v=\varepsilon$ で $q\xrightarrow{\varepsilon}q$ が成り立つ。
4 行目:$\Sigma=\{a\}$、$\mathcal A_1$ は状態 $x,y$ を交互に通り $F_1=\{x\}$、$\mathcal A_2$ は状態 $x',y'$ を交互に通り $F_2=\{y'\}$ とする。どちらも $a^\omega$ を受理するが、積の走りは $(x,x')$ と $(y,y')$ しか通らず、$F_1\times F_2=\{(x,y')\}$ を通らない。
5 行目:$\Sigma=\{a,b\}$、$Q=\{s,f\}$、$I=\{s\}$、$F=\{f\}$ とし、$b$ で $s$ と $f$ が入れ替わり、$a$ では動かない決定性の自動機械を考える。$R_{aa}=R_{bb}$ は恒等関係だが、$(bb)^\omega$ は受理され、$(aa)^\omega$ は受理されない。$R^F_{bb}$ は $(s,s)$ を含み、$R^F_{aa}$ は含まない。
6 行目:$i< j< k$ について、$\{i,j\}$ と $\{i,k\}$ の色 $j-i$ と $k-i$ は異なる。

関連項目

参考文献

[1]
Moshe Y. Vardi, An automata-theoretic approach to linear temporal logic, Logics for Concurrency, Lecture Notes in Computer Science, 1996, pp. 238–266、§2.2 Büchi 自動機械(Proposition 5〜10、Proposition 7 と 10 のあとの計算量の説明)、§2.4(Proposition 13、14)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する