Automi alternanti e model checking

Automi alternanti e model checking

Angelo Montanari (e Stefano Tognazzi) Universit`a di Udine

Indice

Automi di Buechi su parole infinite

Automi alternanti di Buechi su parole infinite Automi di Buechi su alberi infiniti

Automi alternanti di Buechi su alberi infiniti Automi alternanti deboli

LTL e automi alternanti CTL e automi alternanti deboli Model checking per LTL Model checking per CTL

Automi di Buechi su parole infinite

Un automa (non deterministico) di Buechi su parole infinite A `e una quintupla (Σ, S, s⁰, ρ, F ), dove:

I Σ `e un alfabeto finito di simboli non vuoto;

I S `e un insieme finito di stati non vuoto;

I s⁰∈ S `e lo stato iniziale;

I ρ : S × Σ → 2^S `e una funzione di transizione: ρ(s, a) `e l’insieme di stati che A pu`o raggiungere a partire dallo stato s in corrispondenza del carattere a; alternativamente, la

funzione di transizione pu`o essere vista come una relazione ρ ⊆ S × Σ × S.

I F ⊆ S `e l’insieme degli stati finali.

Il linguaggio riconosciuto da A viene indicato con L(A).

Risultati di base

Proposizione

Si assuma che A1 e A2 siano due automi (non deterministici) di Buechi, rispettivamente con n1 e n2 stati. `E possibile costruire un automa (non deterministico) di Buechi A, con O(n₁· n₂) stati, tale che L(A) = L(A1) ∩ L(A2).

Proposizione

1. Il problema del vuoto per gli automi (non deterministici) di Buechi `e decidibile in tempo lineare (rispetto al numero di stati dell’automa).

2. Il problema di stabilire se esistono delle parole riconosciute da un automa (non deterministico) di Buechi con n stati `e decidibile in spazio O(log²n).

Formule Booleane positive

Dato un insieme X di variabili proposizionali, sia B⁺(X ) l’insieme delle formule Booleane positive costruite a partire da X , ossia costruite a partire dagli elementi di X utilizzando ∧ (congiunzione) e ∨ (disgiunzione). Per comodit`a, assumiamo che B⁺(X ) contenga anche le costanti logiche true e false.

Sia Y ⊆ X . Diremo che Y soddisfa ϕ ∈ B⁺(X ) se l’assegnamento del valore di verit`a vero alle variabili proposizionali in Y e falso alle variabili proposizionali in X \ Y rende vera la formula ϕ.

Esempio. Si consideri la formula ϕ = (s1∨ s₂) ∧ (s3∨ s₄). Gli insiemi {s1, s3} e {s₁, s4} rendono entrambi vera ϕ.

Formule Booleane positive e funzione di transizione

Si consideri un automa (non deterministico) di Buechi A = (Σ, S, s⁰, ρ, F ) e sia ρ(s, a) = {s1, s2, s3}. Ogni stato s⁰ in ρ(s, a) pu`o essere visto come una delle possibili scelte non deterministiche dell’automa per il prossimo stato. Tale situazione pu`o essere rappresentata mediante la seguente formula di B⁺(S):

s1∨ s₂∨ s₃

Negli automi di Buechi alternanti ρ(s, a) pu`o essere una qualunque formula di B⁺(S). Ad esempio, la transizione:

ρ(s, a) = (s₁∧ s₂) ∨ (s₃∧ s₄)

specifica che A accetta la parola aw (con a ∈ Σ e w ∈ Σ^∗), quando si trova nello stato s, se esso accetta la parola w a partire sia da s1 che da s2 oppure a partire sia da s3 che da s4.

Automi alternanti di Buechi su parole infinite

Formalmente, un automa alternante di Buechi su parole infinite `e una quintupla A = (Σ, S, s<sup>0</sup>, ρ, F ), dove tutte le componenti, ad eccezione della funzione di transizione ρ, sono definite come nel caso degli automi (non deterministici) di Buechi e la funzione di transizione ρ `e della forma: ρ : S × Σ → B⁺(S).

Data la presenza di scelte universali (∧) accanto a scelte

esistenziali (∨) nella funzione di transizione degli automi alternanti, un run di un automa alternante non `e una parola, ma un albero.

Pi`u precisamente, un run r di un automa alternante di Buechi su una parola infinita α = a<sub>0</sub>a<sub>1</sub>. . . `e un albero infinito etichettato con simboli dell’insieme degli stati S tale che:

I r () = s⁰;

I se |x | = i , r (x ) = s e ρ(s, ai) = θ, allora x ha k figli x1, . . . , x_k, per qualche k ≤ |S|, e {r (x₁), . . . , r (x_k)} soddisfa θ.

Un esempio

Sia ρ(s₀, a₀) = (s₁∨ s₂) ∧ (s₃∨ s₄). I nodi dell’albero di

computazione a livello 1 conterranno l’etichetta s1 o l’etichetta s2

e anche l’etichetta s₃ o l’etichetta s₄.

Un run pu`o contenere anche rami finiti: se |x | = i , r (x ) = s e ρ(s, ai) = true, allora x pu`o essere privo di figli. Al contrario, non

`e possibile che ρ(s, a<sub>i</sub>) = false dal momento che false non `e soddisfacibile. Chiediamo, inoltre, la completezza della funzione di transizione, ossia escludiamo la possibilit`a che ρ(s, ai) sia indefinita per qualche s ∈ S e a_i ∈ Σ.

La condizione di accettazione per gli automi di Buechi alternanti `e pertanto definita nel seguente modo: ogni cammino infinito in r include un numero infinito di occorrenze di almeno uno stato finale.

Problema del (non) vuoto per automi alternanti di Buechi

Proposizione

Sia A un automa alternante di Buechi con n stati. `E possibile costruire un automa (non deterministico) di Buechi And con 2^O(n) stati tale che L(A_nd) = L(A).

Proposizione

1. Il problema del (non) vuoto per gli automi alternanti di Buechi `e decidibile in tempo esponenziale.

2. Il problema del (non) vuoto per gli automi alternanti di Buechi `e decidibile in spazio quadratico.

Automi di Buechi su alberi infiniti

Un automa (non deterministico) di Buechi su alberi infiniti di arit`a D `e una sestupla A = (Σ, D, S, s⁰, ρ, F ), dove:

I Σ `e un alfabeto finito di simboli;

I D ⊂ N `e un insieme finito di ariet`a;

I S `e un insieme finito di stati;

I s⁰∈ S `e lo stato iniziale;

I ρ `e una funzione di transizione della forma

ρ : S × Σ × D → 2^S∗, dove ρ(s, a, k) ∈ S^k for each s ∈ S, a ∈ Σ, and k ∈ D;

I F ⊆ S `e l’insieme degli stati finali.

Denotiamo con T (A) l’insieme degli alberi riconosciuti da A.

Problema del (non) vuoto per automi di Buechi su alberi infiniti

Proposizione

Il problema del (non) vuoto per gli automi (non deterministici) di Buechi su alberi infiniti `e decidibile in tempo quadratico.

Automi alternanti di Buechi su alberi infiniti

I Una automa alternante di Buechi su alberi infiniti A `e una sestupla (Σ, D, S, s⁰, ρ, F ), dove tutte le componenti, a parte ρ, sono definite come nel caso degli automi di Buechi (non deterministici) su alberi infiniti.

I ρ `e una funzione parziale ρ : S × Σ × D → B<sup>+</sup>(N × S), dove ρ(s, a, k) ∈ B<sup>+</sup>({1, . . . , k} × S) per ogni s ∈ S, a ∈ Σ, k ∈ D per i quali ρ(s, a, k) `e definita.

Esempio. Sia ρ(s, a, 2) = ((1, s₁) ∨ (2, s₂)) ∧ ((1, s₃) ∨ (2, s₁)). A pu`o scegliere fra 4 alternative: nella prima una ‘copia’ di A procede in direzione 1 nello stato s1 e un’altra in direzione 1 nello stato s<sub>3</sub>; nella seconda una procede in direzione 1 nello stato s<sub>1</sub> e un’altra in direzione 2 nello stato s<sub>1</sub>; nella terza una procede in direzione 2 nello stato s2 e un’altra in direzione 1 nello stato s3; nella quarta una procede in direzione 2 nello stato s<sub>2</sub> e un’altra in direzione 2 nello stato s<sub>1</sub>. Si noti come pi`u copie possano

procedere nella stessa direzione.

Run degli automi alternanti di Buechi su alberi infiniti

Un run r di un automa alternante di Buechi su alberi infiniti con etichette in Σ e ariet`a in D `e un albero infinito con etichette in N^∗× S. Sia t = hτ, T i, dove τ `e il dominio e T `e la funzione di etichettatura, l’albero di input e sia r = hτ_r, T_ri. Ogni nodo di τ_r corrisponde ad un nodo di τ , mentre un nodo di τ pu`o essere associato a pi`u nodi di τ_r (un nodo di τ_r, etichettato con (x , s), descrive una copia di A che legge il nodo x di τ nello stato s).

Formalmente, hτr, Tri deve soddisfare le seguenti condizioni:

1. T_r() = (, s⁰);

2. sia y ∈ τr, Tr(y ) = (x , s), arity (x ) = k, ρ(s, T (x ), k) = θ;

allora, deve esistere un insieme

Q = {(c1, s1), . . . , (cn, sn)} ⊆ {1, . . . , k} × S tale che:

I Q soddisfa θ;

I per ogni 1 ≤ i ≤ n vi `e un nodo y · i ∈ τr e Tr(y · i ) = (x · ci, si).

Un esempio

Sia t = hτ, T i un albero con

I arity () = 2

I T () = a

I ρ(s⁰, a, 2) = ((1, s1) ∨ (1, s2)) ∧ ((1, s3) ∨ (1, s1)) I nodi di r = hτ_r, T_ri a livello 1 includeranno

I l’etichetta (1, s1) o l’etichetta (1, s2) e

I l’etichetta (1, s3) o l’etichetta (1, s1)

Il problema del (non) vuoto per gli automi alternanti di Buechi su alberi infiniti

Proposizione

Sia A un automa alternante di Buechi su alberi infiniti con n stati.

E possibile costruire un automa (non deterministico) di Buechi su` alberi infiniti A_nd con 2^{O(n log n)} stati tale che T (A) = T (A_nd).

Proposizione

Il problema del (non) vuoto per gli automi alternanti di Buechi su alberi infiniti `e decidibile in tempo esponenziale.

Automi di Buechi su alberi infiniti su un alfabeto con una sola lettera

Il problema del (non) vuoto per gli automi (non deterministici) di Buechi su alberi infiniti `e riducibile al problema del (non) vuoto per gli automi (non deterministici) di Buechi su alberi infiniti

etichettati con simboli di un alfabeto con una sola lettera.

Idea: anzich´e controllare che il linguaggio riconosciuto da un automa A = (Σ, D, S, s⁰, ρ, F ) non sia vuoto, si controlla che non sia vuoto il linguaggio riconosciuto dall’automa A⁰ = ({a}, D, S, s⁰, ρ⁰, F ), dove, per ogni s ∈ S e k ∈ D, ρ⁰(s, a, k) =^S_b∈Σρ(s, b, k).

`E facile vedere che A accetta qualche albero se e solo se A⁰ accetta qualche albero a-etichettato: a partire da una

computazione di successo di A⁰, `e possibile costruire un albero di input sul quale la computazione di successo A<sup>0</sup> `e anche una computazione di successo per A; il viceversa segue

immediatamente dalla definizione di ρ⁰.

Tale riduzione non pu` o essere applicata agli automi alternanti (in generale)

Si supponga di definire A⁰ come nel caso degli automi di Buechi su alberi infiniti, con ρ⁰(s, a, k) =^S_b∈Σρ(s, b, k).

Se A⁰ accetta qualche albero a-etichettato, non `e detto che A accetti qualche albero.

Una condizione necessaria per la validit`a della riduzione `e, infatti, che copie diverse di A⁰ che operano sullo stesso sottoalbero di input t assumano la stessa etichettatura per t.

Niente impedisce, per`o, che una copia di A⁰ assuma una certa etichettatura di t e un’altra copia di A⁰ assuma un’etichettatura diversa di t.

Automi alternanti di Buechi su alberi infiniti su un alfabeto con una sola lettera

Una possibile via d’uscita: il problema di cui al lucido precedente non si pone nel caso in cui A sia definito su un alfabeto con una singola lettera.

In alcuni casi concreti di interesse, gli automi alternanti di Buechi si trovano ad operare su alberi infiniti su un alfabeto con una sola lettera.

Proposizione

Il problema del (non) vuoto per gli automi alternanti di Buechi su alberi infiniti su un alfabeto di un solo carattere `e decidibile in tempo quadratico.

Automi alternanti deboli

Gli automi alternanti deboli sono una sottoclasse degli automi alternanti di Buechi su alberi infiniti tale che:

I esiste una partizione dell’insieme degli stati S negli insiemi S₁, . . . , S_n (il numero di insiemi della partizione `e detto profondit`a dell’automa) tale che, per 1 ≤ i ≤ n, Si ⊆ F (insieme accettante) oppure Si∩ F = ∅ (insieme rigettante) ed

I `e possibile definire un ordinamento parziale ≤ degli insiemi S₁, . . . , S_n tale che, per ogni s ∈ S_i e s⁰ ∈ S_j, se

s⁰ ∈ ρ(s, a, k), per qualche a ∈ Σ e k ∈ D, allora S_j ≤ S_i. Ne segue che ogni cammino infinito in un run di un automa alternante debole finisce intrappolato in un qualche insieme Si. Ci`o consente di concludere che un cammino `e di successo se e solo se l’insieme S_i in cui rimane intrappolato `e un insieme accettante.

Il problema del (non) vuoto per automi alternanti deboli su un alfabeto con una sola lettera

Proposizione

Il problema del (non) vuoto per automi alternanti deboli su alberi infiniti su un alfabeto con una sola lettera `e decidibile in tempo lineare.

Automi alternanti deboli con alternanza limitata

Esiste una sottoclasse degli automi alternanti deboli di particolare interesse che contiene gli automi alternanti deboli con alternanza limitata. In tali automi, ogni insieme S_i della partizione pu`o essere classificato come transiente, esistenziale o universale.

Per ogni insieme Si, s ∈ Si, a ∈ Σ e k ∈ D, si ha che:

I se S_i `e transiente, allora ρ(s, a, k) non contiene elementi di S_i;

I se S_i `e esistenziale, allora gli elementi di S_i in ρ(s, a, k) sono legati in maniera disgiuntiva (equivalentemente, se la

transizione viene riscritta in forma normale disgiuntiva, in ogni disgiunto compare al pi`u un elemento di S_i);

I se Si `e universale, allora gli elementi di Si in ρ(s, a, k) sono legati in maniera congiuntiva (equivalentemente, se la transizione viene riscritta in forma normale congiuntiva, in ogni congiunto compare al pi`u un elemento di Si).

Il problema del (non) vuoto per automi alternanti deboli con alternanza limitata su un alfabeto con una sola lettera

Dalla definizione di automi alternanti deboli con alternanza

limitata segue che un’alternanza pu`o presentarsi solo nel passaggio da un insieme S<sub>i</sub> all’insieme successivo (ossia da uno stato che `e legato in maniera congiuntiva agli stati dell’insieme cui appartiene ad uno stato che `e legato in maniera disgiuntiva agli stati

dell’insieme cui appartiene, e viceversa).

In altri termini, quando una copia di un automa visita uno stato in un insieme esistenziale (rispettivamente, universale) Si, essa procede in modo esistenziale (rispettivamente, universale) fino a quando rimane in S_i.

Proposizione

Il problema del (non) vuoto per automi alternanti deboli con alternanza limitata di dimensione n e profondit`a m su un alfabeto con una sola lettera pu`o essere risolto in spazio O(m · log²n).

LTL e automi alternanti: traduzione - 1

I modelli di una formula della Logica Temporal Lineare (LTL) possono essere visti come computazioni (una computazione `e una funzione π : ω → 2<sup>AP</sup>, dove AP `e l’insieme delle variabili

proposizionali).

`E possibile dimostrare che le computazioni che soddisfano una data formula sono esattamente quelle accettate da un automa che opera su parole infinite.

Proposizione

Data una formula ϕ di LTL, `e possibile costruire un automa alternante di Buechi su parole infinite A<sub>φ</sub>= (Σ, S, s<sup>0</sup>, ρ, F ), con Σ = 2<sup>AP</sup> e |S| ∈ O(|ϕ|), tale che L(Aϕ) `e esattamente l’insieme delle computazioni che soddisfano la formula ϕ.

LTL e automi alternanti: traduzione - 2

I L’insieme degli stati S consiste di tutte le sottoformule di ϕ e delle loro negazioni (identifichiamo ¬¬ψ con ψ).

I Lo stato iniziale s⁰ `e esattamente ϕ.

I L’insieme degli stati finali F consiste di tutti gli stati/formule di S della forma ¬(ξUψ).

I Per definire la funzione ρ, introduciamo il duale ¯θ di una formula θ, ottenuto a partire da θ sostituendo ∨ con ∧ (e viceversa), true con false (e viceversa) e negando le sottoformule in S. In modo pi`u formale,

I ξ = ¬ξ per ξ ∈ S¯

I true = false¯

I false = true¯

I (α ∧ β) = ¯α ∨ ¯β (se α ∧ β non appartiene a S)

I (α ∨ β) = ¯α ∧ ¯β (se α ∨ β non appartiene a S)

LTL e automi alternanti: traduzione - 3

La funzione di transizione ρ `e definita nel seguente modo:

I ρ(p, a) = true se p ∈ a

I ρ(p, a) = false se p 6∈ a

I ρ(ξ ∧ ψ, a) = ρ(ξ, a) ∧ ρ(ψ, a)

I ρ(¬ψ, a) = ρ(ψ, a)

I ρ(X ψ, a) = ψ

I ρ(ξUψ, a) = ρ(ψ, a) ∨ (ρ(ξ, a) ∧ ξUψ)

Le regole per true e false sono facilmente derivabili.

Si noti che, nella definizione di ρ(ξUψ, a), il secondo congiunto del secondo disgiunto ξUψ `e uno stato (formula atomica di B⁺(S)).

Un esempio

Consideriamo la formula ϕ = ¬(pUq), con p, q ∈ AP, e la

computazione π = {p}^ω in cui p `e sempre vero e q `e sempre falso.

`E immediato vedere che la computazione π soddisfa ϕ.

La funzione di transizione ρ per A_φ, conterr`a la seguente transizione: ρ(¬(pUq), {p}) = ρ(q, {p}) ∨ (ρ(p, {p}) ∧ pUq) = false ∨ (true ∧ pUq) = pUq = (pUq `e (una sottoformula di) ϕ)

¬(pUq)

Esiste una computazione di Aφ su π in cui lo stato finale/

accettante ¬(pUq) si ripete infinite volte (sequenza di stati {¬(pUq)}^ω).

LTL e automi non deterministici di Buechi

Proposizione

Data una formula ϕ di LTL, `e possibile costruire un automa (non deterministico) di Buechi su parole infinite A<sub>nd ϕ</sub> = (Σ, S, s<sup>0</sup>, ρ, F ), dove Σ = 2<sup>AP</sup> e |S| `e in 2^O(|φ|), tale che L(And ϕ) `e esattamente l’insieme delle computazioni che soddisfano la formula ϕ.

Semantica di CTL

La semantica di CTL pu`o essere definita rispetto a programmi (che operano su un insieme di variabili proposizionali AP) della forma P = (W , w⁰, R, V ), dove:

I W `e un insieme di stati (se W `e finito, P `e detto programma a stati finiti);

I w⁰ ∈ W `e uno stato iniziale;

I R ⊆ W² `e una relazione di accessibilit`a totale (assumiamo la totalit`a per ragioni di natura tecnica);

I V : W → 2^AP `e una funzione che, dato uno stato, specifica quali variabili proposizionali sono vere in quello stato.

Un cammino in P `e una sequenza di stati u<sub>0</sub>, u<sub>1</sub>, . . . tale che, per ogni i ≥ 0, vale R(u<sub>i</sub>, u<sub>i +1</sub>). La relazione |= `e definita nel modo usuale.

CTL e automi alternanti deboli con alternanza limitata:

traduzione - 1

Un programma P `e detto programma ad albero se (l’unfolding del grafo) (W , R) `e un albero con radice w⁰. Se (l’unfolding di) (W , R) `e un albero D-ario, allora P `e un albero D-ario infinito (R

`e totale) etichettato con elementi in 2^AP.

`E possibile dimostrare che i programmi ad albero che soddisfano una data formula sono esattamente quelli accettati da un automa alternante debole con alternanza limitata.

Proposizione

Dati una formula ϕ di CTL e un insieme finito D ⊂ N, `e possibile costruire un automa alternante debole con alternanza limitata A<sub>ϕ</sub>= (Σ, D, S, s<sup>0</sup>, ρ, F ), dove Σ = 2<sup>AP</sup> e |S| `e in O(|φ|), tale che T (Aφ) `e esattamente l’insieme dei programmi ad albero D-ari che soddisfano ϕ.

CTL e automi alternanti deboli con alternanza limitata:

traduzione - 2

I L’insieme degli stati S consiste di tutte le sottoformule di ϕ e delle loro negazioni (identifichiamo ¬¬ψ con ψ).

I Lo stato iniziale s⁰ `e ϕ.

I L’insieme F `e composto da tutti gli stati/formule in S della forma ¬E (ξUψ) e ¬A(ξUψ).

I Per definire la funzione ρ, introduciamo il duale ¯θ di una formula θ, definito come nel caso di LTL:

I ρ(p, a, k) = true se p ∈ a

I ρ(p, a, k) = false se p 6∈ a

I ρ(¬ψ, a, k) = ρ(ψ, a, k)

I ρ(ξ ∧ ψ, a, k) = ρ(ξ, a, k) ∧ ρ(ψ, a, k)

I ρ(EX φ, a, k) =Wk c=1(c, φ)

I ρ(AX φ, a, k) =Vk c=1(c, φ)

I ρ(E (ξUψ), a, k) = ρ(ψ, a, k) ∨ (ρ(ξ, a, k) ∧Wk

c=1(c, E (ξUψ)))

I ρ(A(ξUψ), a, k) = ρ(ψ, a, k) ∨ (ρ(ξ, a, k) ∧Vk

c=1(c, A(ξUψ)))

CTL e automi alternanti deboli con alternanza limitata:

traduzione - 3

Infine, la partizione degli stati di A_ϕ e l’ordinamento (parziale) delle classi della partizione sono definiti nel seguente modo:

I lo stato/formula ψ in S costituisce un insieme singoletto {ψ}

della partizione;

I l’ordinamento parziale `e definito nel seguente modo:

{ξ} ≤ {ψ} se e solo se ξ `e una sottoformula o la negazione di una sottoformula di ψ;

I tutti gli insiemi della partizione sono transienti, ad eccezione degli insiemi della forma {E (ξUψ)} o della forma

{¬A(ξUψ)}, che sono esistenziali, e degli insiemi della forma {A(ξUψ)} o della forma {¬E (ξUψ)}, che sono universali.

Model checking per LTL

Dati un programma a stati finiti e una formula ϕ di LTL che specifica le computazioni ammissibili (del programma), il problema del model checking consiste nello stabilire se tutte le computazioni del programma sono ammissibili.

I Sia u = u₀, u₁, . . . un cammino di un programma a stati finiti P = (W , w⁰, R, V ) tale che u0= w⁰.

I Definiamo computazione di P la sequenza V (u0), V (u1), . . . .

I Diremo che P soddisfa una formula ϕ di LTL se tutte le computazioni di P soddisfano ϕ.

Il problema del model checking per LTL `e il problema di stabilire se P soddisfa o meno ϕ.

Model checking per LTL: passi intermedi - 1

L’automa A_P per il programma P.

I Un programma P = (W , w⁰, R, V ) pu`o essere visto come un automa (non deterministico) di Buechi A_P = (Σ, W , w⁰, ρ, W ), dove Σ = 2^AP e v ∈ ρ(u, a) se e solo se uRv e a = V (u).

I Dato che l’insieme degli stati finali coincide con l’insieme di tutti gli stati, ogni run infinito di A_P `e di successo

(accettante) e, quindi, L(A_P) `e l’insieme di tutte le computazioni di P.

L’automa A_ϕ per la formula ϕ di LTL.

I Per ogni formula ϕ di LTL, `e possibile costruire un automa A<sub>ϕ</sub> tale che L(Aϕ) `e esattamente l’insieme delle computazioni che soddisfano la formula φ.

Model checking per LTL: passi intermedi - 2

I Date le propriet`a di chiusura rispetto all’intersezione e alla complementazione degli automi (non deterministici) di

Buechi, il problema di verificare se L(AP) ⊆ L(Aϕ) (problema del model checking) `e equivalente al problema di verificare se l’intersezione delle computazioni accettate da A<sub>P</sub> e di quelle che rendono falsa ϕ `e vuota, ossia al problema del vuoto per L(A_P) ∩ L(A_ϕ).

I Per costruire L(A_φ) si considerino le seguenti uguaglianze:

L(A_φ) = L(A_φ) = Σ^ω− L(A_φ).

I E possibile costruire un automa A` ¬φ che accetta il linguaggio L(A_φ) con 2^O(|φ|) stati.

I Infine, `e possibile costruire un automa che riconosce il linguaggio intersezione L(A_P) ∩ L(A¬φ) con O(|W | · 2^O(|φ|)) stati.

Un algoritmo di model checking basato su automi per LTL

Proposizione

Stabilire se un programma a stati finiti P soddisfa una formula ϕ di LTL pu`o essere fatto in tempo O(|P| · 2^O(|ϕ|)) e in spazio O((|ϕ| + log |P|)²).

Si noti che la complessit`a temporale `e polinomiale nella dimensione del programma ed esponenziale nella dimensione della formula (specifica).

Dato che la dimensione della formula `e di norma sufficientemente ridotta, tale soluzione si dimostra effettivamente praticabile – si veda il sistema Aalta (Another Algorithm for LTL To Buechi Automata).

Model checking per CTL

Nel caso delle logiche temporali ramificate, come CTL, ogni programma corrisponde ad un singolo albero di computazione.

Il model checking si riduce alla verifica dell’accettazione di tale albero di computazione da parte dell’automa che descrive la formula (specifica).

Model checking per CTL: passi intermedi - 1

I Un programma P = (W , w⁰, R, V ) pu`o essere visto come un albero hτ_P, TPi, con etichette in W , ottenuto attraverso l’unfolding di P a partire dallo stato iniziale w⁰.

I Per ogni w in W , definiamo arity (w ) come il numero dei suoi successori rispetto alla relazione R.

I Sia succR(w ) = (w1, . . . , w_{arity (w )}) la lista ordinata dei successori di w (assumiamo che i nodi di W siano ordinati).

I τ_P e TP possono essere definiti induttivamente nel seguente modo:

I  ∈ τ_P e T_P() = w⁰;

I per y ∈ τ_P, con succ_R(T_P(y )) = (w₁, . . . , w_k), e per ogni 1 ≤ i ≤ k, y · i ∈ τP e TP(y · i ) = wi.

Model checking per CTL: passi intermedi - 2

I L’albero del programma pu`o essere successivamente trasformato in un albero D-ario etichettato con elementi in 2^AP

I Tale albero `e formalmente definito dalla coppia (τP, V · TP), dove V · T_P = V (T_P(y )), con y ∈ τ_P.

Consideriamo ora una formula ϕ di CTL. Sia AD,ϕ l’automa alternante debole con alternanza limitata che accetta esattamente gli alberi D-ari che soddisfano la formula ϕ.

`E facile vedere che (τ<sub>P</sub>, V · T<sub>P</sub>) `e accettato da AD,ϕ se e solo se P |= ϕ.

Mostriamo, ora, che l’automa prodotto di P e AD,ϕ`e un automa alternante debole con alternanza limitata su un alfabeto di una lettera che `e non vuoto se e solo se (τ_P, V · T_P) `e accettato da A_D,ϕ.

Model checking per CTL: passi intermedi - 3

I Sia AD,ϕ= (2^AP, D, S, ϕ, ρ, F ) e sia S1, . . . , Sn la partizione di S.

I L’automa prodotto di P e AD,ϕ`e l’automa AP,ϕ= ({a}, D, W × S, (w⁰, ϕ), δ, G ), dove:

I dati s ∈ S, w ∈ W , succR(w ) = (w1, . . . , wk) e ρ(s, V (w ), k)

= θ, definiamo δ((w , s), a, k) = θ⁰, dove θ⁰ `e ottenuta da θ sostituendo ogni atomo (c, s⁰) presente in θ con l’atomo (c, (w_c, s⁰));

I G = W × F ;

I W × S `e partizionato in W × S₁, W × S₂, . . . , W × S_n;

I per 1 ≤ i ≤ n, W × S_i `e transiente (rispettivamente, esistenziale, universale) se S<sub>i</sub> `e transiente (rispettivamente, esistenziale, universale).

Si noti che se P ha m₁ stati e AD,ϕ ha m₂ stati, allora A_P,φ ha O(m1· m₂) stati.

Un algoritmo di model checking per CTL basato su automi

Proposizione

T (AP,φ) non `e vuoto se e solo se P |= φ

Proposizione

Stabilire se un programma a stati finiti P soddisfa una formula ϕ di CTL pu`o essere fatto in tempo O(|P| · |φ|) e spazio

O(|φ| · log²|P|).