LTLフォーミュラ用のGNBAを構築する時間

Question

GNBAを構築する証拠に問題があります（一般化された非決定的ビュチオートマトン） のために LTLフォーミュラ:

定理： 任意のLTLフォーミュラ$ varphi $には、gnba $ g _ { varphi} $ over alphabet $ 2^{ap} $が存在します。

1. $ operatorname {word}（ varphi）= l _ { omega}（g _ { varphi}）$。

2. $ g _ { varphi} $は、時間とスペースで$ 2^{o（| varphi |）} $で共有できます。ここで、$ | varphi | $は$ varphi $のサイズです。

3. $ g _ { varphi} $の受け入れ状態の数は、$ o（| varphi |）$で上記で囲まれています。

私の問題は（2）の証明にあります。つまり、$ g _ { varphi} $の状態の数は$ 2^{| operatorname {subf}（ varphi）|}で区切られていると書かれています。 $ but but von $ | operatorname {subf}（ varphi）| leq 2 cdot | varphi | $（$ operatorname {subf}（ varphi）$はすべてのサブフォーミュラのセットです）状態の数は$ 2^{o（| varphi |）} $で区切られています。

しかし、なぜ$ | operatorname {subf}（ varphi）| leq 2 cdot | varphi | $ hold？

Answer 1

一般に、論理式は木と考えることができます。内部ノードは演算子であり、葉は原子命題です。したがって、すべての式は、その最上位オペレーターのアリティと同じように多くの直接サブフォーミュ（最初のレベル）で構成されています。例えば、

$ qquad varphi land psi $

2つの直接サブフォーミュラ$ varphi $と$ psi $があります。これは再帰的に継続することができ、私たちはそれを見ることができます

$ qquad displaystyle | operatorname {subf}（ varphi）| leq sum _ { circ in operatorname {op}（ varphi）} operatorname {arity}（ circ）$、

ここで、$ operatorname {op}（ varphi）$は、$ varphi $で発生する演算子のマルチセットです。非公式に言えば、すべてのオペレーターはそのオペランドをサブフォーメーレのセットに寄付します。サブフォーミュラが複数回発生する可能性があるため、$ leq $ではなく$ = $ $ではないことに注意してください。

LTLでは、すべてのオペレーターが最大のアリティ2を持っているため、$ | operatorname {subf}（ varphi）| leq 2 | varphi | $は、$ |。| $カウント（少なくとも）オペレーターの発生を提供しました。