È ora di costruire un GNBA per LTL formula

Question

Ho un problema con la prova per la costruzione di un GNBA ( generalizzata non deterministico Büchi automa ) per un LTL formula :

Teorema: Per ogni LTL Formula $ \ varphi $ esiste un GNBA $ G _ {\ varphi} $ nel corso alfabeto $ di 2 ^ {AP} $ tale che:

1. $ \ operatorname {Word} (\ varphi) = L _ {\ omega} (G _ {\ varphi}) $.

2. $ G _ {\ varphi} $ può essere racchiuso in cassetta tempo e nello spazio $ di 2 ^ {O (| \ varphi |)} $, dove $ | \ varphi |. $ È la dimensione di $ \ varphi $

3. Il numero di stati che accettano di $ G _ {\ varphi} $ è delimitata superiormente da $ O (| \ varphi |). $

Il mio problema sta nella prova di (2), che è, nella prova si dice che il numero di stati in $ G _ {\ varphi} $ è delimitata da $ 2 ^ {| \ operatorname {subf} (\ varphi ) |} $, ma dal momento che $ | \ operatorname {subf} (\ varphi) | \ Leq 2 \ cdot | \ varphi | $ (dove $ \ operatorname {subf} (\ varphi) $ è l'insieme di tutte subformulae) il numero di stati è delimitata da $ 2 ^ {O (| \ varphi |)} $.

Ma perché $ | \ operatorname {subf} (\ varphi) | \ Leq 2 \ cdot | \ varphi | $ attesa?

Answer 1

, formule logiche generali può essere pensato come alberi; i nodi interni sono gli operatori e le foglie sono proposizioni atomiche. Pertanto, ogni formula consiste altrettanti subformulae diretta (che è al primo livello) come più in alto arit'a dell'operatore. Ad esempio,

$ \ qquad \ varphi \ terra \ psi $

ha due subformulae diretta $ \ varphi $ e $ \ psi $. Questo può essere continuata in modo ricorsivo e vediamo che

$ \ qquad \ displaystyle | \ operatorname {subf} (\ varphi) | \ Leq \ somma _ {\ circ \ in \ operatorname {op} (\ varphi)} \ {operatorname arity} (\ circ) $,

dove $ \ operatorname {op} (\ varphi) $ è il multi-insieme di operatori che si verificano in $ \ varphi $. Informalmente parlando, ogni operatore contribuisce suoi operandi alla serie di subformulae. Si noti che abbiamo $ \ leq $ e non $ = $ a causa di un sottoformula potrebbe avvenire più volte.

In LTL, tutti gli operatori hanno al massimo arity due, quindi $ | \ operatorname {subf} (\ varphi) | \ Leq 2 | \ varphi | $ a condizione che $ |. |. $ Conta (almeno) le occorrenze operatore