是时候为LTL公式构建GNBA

Question

我对构建GNBA的证据有问题（广义非确定性Büchi自动机） 为一个 LTL公式:

定理： 对于任何LTL公式$ varphi $，都存在Alphabet $ 2^{AP} $的Gnba $ g _ { varphi} $，这样

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

2. $ g _ { varphi} $可以在时间和空间中构建$ 2^{o（| varphi |）} $，其中$ | varphi | $是$ varphi $的大小。

3. $ g _ { varphi} $的接受状态的数量在上面由$ o（| varphi |）$界定。

我的问题在于（2）的证明，也就是说，在证明中，它说$ g _ { varphi} $中的状态数是由$ 2^{| operatoTorname {subf}（ varphi）|}界限的。 $，但由于$ | 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 $

有两个直接的subformulae $ varphi $和$ psi $。这可以递归继续，我们看到

$ qquad displayStyle | operatatorName {subf}（ varphi）| leq sum _ { circ in operatatorName {op}（ varphi）}} operatatorName {arity}（ circ）$，

其中$ operatatorName {op}（ varphi）$是$ varphi $中发生的多种运算符。从非正式的角度来看，每个操作员都为子形式的一组贡献了其操作数。请注意，我们有$ leq $，而不是$ = $，因为可能会多次发生。

在LTL中，所有运营商最多都有两个，因此$ | operatotorname {subf}（ varphi）| leq 2 | varphi | $提供了$ |。| $ counts（至少）操作员出现。