Introduction to Formal Methods Chapter 06: Fair CTL Model Checking
Roberto Sebastiani and Stefano Tonetta
DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it URL: http://disi.unitn.it/rseba/DIDATTICA/fm2020/
Teaching assistant: Enrico Magnago – enrico.magnago@unitn.it
CDLM in Informatica, academic year 2019-2020
last update: Monday 18thMay, 2020, 14:48
Copyright notice: some material (text, figures) displayed in these slides is courtesy of R. Alur, M. Benerecetti, A. Cimatti, M.
Di Natale, P. Pandya, M. Pistore, M. Roveri, and S.Tonetta, who detain its copyright. Some exampes displayed in these slides are taken from [Clarke, Grunberg & Peled, “Model Checking”, MIT Press], and their copyright is detained by the authors. All the other material is copyrighted by Roberto Sebastiani. Every commercial use of this material is strictly forbidden by the copyright laws without the authorization of the authors. No copy of these slides can be displayed in public
Outline
1 Fair CTL Model Checking: Generalities
2 Checking Fair EG (Explicit-State)
3 Checking Fair EG (Symbolic)
Fair CTL Model Checking: Generalities
Outline
1 Fair CTL Model Checking: Generalities
2 Checking Fair EG (Explicit-State)
3 Checking Fair EG (Symbolic)
Fair CTL Model Checking: Generalities
Fairness/Justice
An event E occurs infinitely often. Example:
Let R i be true iff the process i is running.
Fairness: every process runs infinitely often.
^
i
GFR i
(It is often used as condition for other properties.) You cannot express the condition in CTL:
GFφ = AGAFφ,
but (GFφ) → ψ 6= (AGAFφ) → ψ, because FGφ
06= EFEGφ
0.
There is no CTL formula equivalent to FGφ
(FGφ 6= AFAGφ and FGφ 6= EFEGφ).
Fair CTL Model Checking: Generalities
Fairness/Justice
An event E occurs infinitely often. Example:
Let R i be true iff the process i is running.
Fairness: every process runs infinitely often.
^
i
GFR i
(It is often used as condition for other properties.) You cannot express the condition in CTL:
GFφ = AGAFφ,
but (GFφ) → ψ 6= (AGAFφ) → ψ, because FGφ
06= EFEGφ
0.
There is no CTL formula equivalent to FGφ
(FGφ 6= AFAGφ and FGφ 6= EFEGφ).
Fair CTL Model Checking: Generalities
Fairness/Justice
An event E occurs infinitely often. Example:
Let R i be true iff the process i is running.
Fairness: every process runs infinitely often.
^
i
GFR i
(It is often used as condition for other properties.) You cannot express the condition in CTL:
GFφ = AGAFφ,
but (GFφ) → ψ 6= (AGAFφ) → ψ, because FGφ
06= EFEGφ
0.
There is no CTL formula equivalent to FGφ
(FGφ 6= AFAGφ and FGφ 6= EFEGφ).
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
Let M be the KS M = hS, S 0 , R, L, APi and M f the fair version M f = hS, S 0 , R, L, AP, FT i, FT = {F 1 , ..., F n }.
A path is fair iff it visits every F i infinitely often.
Fair CTL model checking restricts the path quantifiers to fair paths:
M
f, s
i|= Aφ iff π |= φ for every fair path π = s
i, s
i+1, ...
M
f, s
i|= Eφ iff π |= φ for some fair path π = s
i, s
i+1, ...
We introduce A f and E f , the restricted versions of the quantifiers A and E:
M
f, s |= Aφ iff M, s |= A
fφ M
f, s |= Eφ iff M, s |= E
fφ
Fair state: a state from which at least one fair path originates, that
is, a state s is a fair state in M f iff M f , s |= EGtrue.
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
Let M be the KS M = hS, S 0 , R, L, APi and M f the fair version M f = hS, S 0 , R, L, AP, FT i, FT = {F 1 , ..., F n }.
A path is fair iff it visits every F i infinitely often.
Fair CTL model checking restricts the path quantifiers to fair paths:
M
f, s
i|= Aφ iff π |= φ for every fair path π = s
i, s
i+1, ...
M
f, s
i|= Eφ iff π |= φ for some fair path π = s
i, s
i+1, ...
We introduce A f and E f , the restricted versions of the quantifiers A and E:
M
f, s |= Aφ iff M, s |= A
fφ M
f, s |= Eφ iff M, s |= E
fφ
Fair state: a state from which at least one fair path originates, that
is, a state s is a fair state in M f iff M f , s |= EGtrue.
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
Let M be the KS M = hS, S 0 , R, L, APi and M f the fair version M f = hS, S 0 , R, L, AP, FT i, FT = {F 1 , ..., F n }.
A path is fair iff it visits every F i infinitely often.
Fair CTL model checking restricts the path quantifiers to fair paths:
M
f, s
i|= Aφ iff π |= φ for every fair path π = s
i, s
i+1, ...
M
f, s
i|= Eφ iff π |= φ for some fair path π = s
i, s
i+1, ...
We introduce A f and E f , the restricted versions of the quantifiers A and E:
M
f, s |= Aφ iff M, s |= A
fφ M
f, s |= Eφ iff M, s |= E
fφ
Fair state: a state from which at least one fair path originates, that
is, a state s is a fair state in M f iff M f , s |= EGtrue.
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
Let M be the KS M = hS, S 0 , R, L, APi and M f the fair version M f = hS, S 0 , R, L, AP, FT i, FT = {F 1 , ..., F n }.
A path is fair iff it visits every F i infinitely often.
Fair CTL model checking restricts the path quantifiers to fair paths:
M
f, s
i|= Aφ iff π |= φ for every fair path π = s
i, s
i+1, ...
M
f, s
i|= Eφ iff π |= φ for some fair path π = s
i, s
i+1, ...
We introduce A f and E f , the restricted versions of the quantifiers A and E:
M
f, s |= Aφ iff M, s |= A
fφ M
f, s |= Eφ iff M, s |= E
fφ
Fair state: a state from which at least one fair path originates, that
is, a state s is a fair state in M f iff M f , s |= EGtrue.
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
Let M be the KS M = hS, S 0 , R, L, APi and M f the fair version M f = hS, S 0 , R, L, AP, FT i, FT = {F 1 , ..., F n }.
A path is fair iff it visits every F i infinitely often.
Fair CTL model checking restricts the path quantifiers to fair paths:
M
f, s
i|= Aφ iff π |= φ for every fair path π = s
i, s
i+1, ...
M
f, s
i|= Eφ iff π |= φ for some fair path π = s
i, s
i+1, ...
We introduce A f and E f , the restricted versions of the quantifiers A and E:
M
f, s |= Aφ iff M, s |= A
fφ M
f, s |= Eφ iff M, s |= E
fφ
Fair state: a state from which at least one fair path originates, that
is, a state s is a fair state in M f iff M f , s |= EGtrue.
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
In order to solve the fair CTL model checking problem, we must be able to compute:
[E
fX(ϕ)]
[E
f(ϕUψ)]
[E
fGϕ].
Suppose we have a procedure Check_FairEG to compute [E f Gϕ].
Let fair = E f Gtrue. (M, s |= E f Gtrue if s is a fair state.) if ϕ is Boolean, then M f , s |= ϕ iff M, s |= (ϕ ∧ fair ) We can rewrite all the other fair operators:
E
fX(ϕ) ≡ EX(ϕ ∧ fair )
E
f(ϕUψ) ≡ E(ϕU(ψ ∧ fair ))
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
In order to solve the fair CTL model checking problem, we must be able to compute:
[E
fX(ϕ)]
[E
f(ϕUψ)]
[E
fGϕ].
Suppose we have a procedure Check_FairEG to compute [E f Gϕ].
Let fair = E f Gtrue. (M, s |= E f Gtrue if s is a fair state.) if ϕ is Boolean, then M f , s |= ϕ iff M, s |= (ϕ ∧ fair ) We can rewrite all the other fair operators:
E
fX(ϕ) ≡ EX(ϕ ∧ fair )
E
f(ϕUψ) ≡ E(ϕU(ψ ∧ fair ))
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
In order to solve the fair CTL model checking problem, we must be able to compute:
[E
fX(ϕ)]
[E
f(ϕUψ)]
[E
fGϕ].
Suppose we have a procedure Check_FairEG to compute [E f Gϕ].
Let fair = E f Gtrue. (M, s |= E f Gtrue if s is a fair state.) if ϕ is Boolean, then M f , s |= ϕ iff M, s |= (ϕ ∧ fair ) We can rewrite all the other fair operators:
E
fX(ϕ) ≡ EX(ϕ ∧ fair )
E
f(ϕUψ) ≡ E(ϕU(ψ ∧ fair ))
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
In order to solve the fair CTL model checking problem, we must be able to compute:
[E
fX(ϕ)]
[E
f(ϕUψ)]
[E
fGϕ].
Suppose we have a procedure Check_FairEG to compute [E f Gϕ].
Let fair = E f Gtrue. (M, s |= E f Gtrue if s is a fair state.) if ϕ is Boolean, then M f , s |= ϕ iff M, s |= (ϕ ∧ fair ) We can rewrite all the other fair operators:
E
fX(ϕ) ≡ EX(ϕ ∧ fair )
E
f(ϕUψ) ≡ E(ϕU(ψ ∧ fair ))
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
In order to solve the fair CTL model checking problem, we must be able to compute:
[E
fX(ϕ)]
[E
f(ϕUψ)]
[E
fGϕ].
Suppose we have a procedure Check_FairEG to compute [E f Gϕ].
Let fair = E f Gtrue. (M, s |= E f Gtrue if s is a fair state.) if ϕ is Boolean, then M f , s |= ϕ iff M, s |= (ϕ ∧ fair ) We can rewrite all the other fair operators:
E
fX(ϕ) ≡ EX(ϕ ∧ fair )
E
f(ϕUψ) ≡ E(ϕU(ψ ∧ fair ))
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
E f X(ϕ) ≡ EX(ϕ ∧ fair ):
fair F
ϕ
E f (ϕUψ) ≡ E(ϕU(ψ ∧ fair )):
Fair CTL Model Checking: Generalities
Fair CTL Model Checking
E f X(ϕ) ≡ EX(ϕ ∧ fair ):
fair F
ϕ
E f (ϕUψ) ≡ E(ϕU(ψ ∧ fair )):
ϕ ϕ ϕ ϕ ϕ ϕ
F
ψ fair
Checking FairEG (Explicit-State)
Outline
1 Fair CTL Model Checking: Generalities
2 Checking Fair EG (Explicit-State)
3 Checking Fair EG (Symbolic)
Checking FairEG (Explicit-State)
SCC-based Check_FairEG
A Strongly Connected Component (SCC) of a directed graph is a maximal subgraph s.t. all its nodes are reachable from each other.
Given a fair Kripke model M, a fair non-trivial SCC is an SCC with at least one edge that contains at least one state for every fair condition
=⇒ all states in a fair (non-trivial) SCC are fair states
Checking FairEG (Explicit-State)
SCC-based Check_FairEG
A Strongly Connected Component (SCC) of a directed graph is a maximal subgraph s.t. all its nodes are reachable from each other.
Given a fair Kripke model M, a fair non-trivial SCC is an SCC with at least one edge that contains at least one state for every fair condition
=⇒ all states in a fair (non-trivial) SCC are fair states
F3
F2
F1
Checking FairEG (Explicit-State)
SCC-based Check_FairEG
A Strongly Connected Component (SCC) of a directed graph is a maximal subgraph s.t. all its nodes are reachable from each other.
Given a fair Kripke model M, a fair non-trivial SCC is an SCC with at least one edge that contains at least one state for every fair condition
=⇒ all states in a fair (non-trivial) SCC are fair states
F3
F2
F1
Checking FairEG (Explicit-State)
SCC-based Check_FairEG (cont.)
Check_FairEG([φ]):
(i) restrict the graph of M to [φ];
(ii) find all fair non-trivial SCCs C i
(iii) build C := ∪ i C i ;
(iv) compute the states that can reach C (Check_EU([φ],C)).
Checking FairEG (Explicit-State)
SCC-based Check_FairEG (cont.)
Check_FairEG([φ]):
(i) restrict the graph of M to [φ];
(ii) find all fair non-trivial SCCs C i
(iii) build C := ∪ i C i ;
(iv) compute the states that can reach C (Check_EU([φ],C)).
Checking FairEG (Explicit-State)
SCC-based Check_FairEG (cont.)
Check_FairEG([φ]):
(i) restrict the graph of M to [φ];
(ii) find all fair non-trivial SCCs C i
(iii) build C := ∪ i C i ;
(iv) compute the states that can reach C (Check_EU([φ],C)).
Checking FairEG (Explicit-State)
SCC-based Check_FairEG (cont.)
Check_FairEG([φ]):
(i) restrict the graph of M to [φ];
(ii) find all fair non-trivial SCCs C i
(iii) build C := ∪ i C i ;
(iv) compute the states that can reach C (Check_EU([φ],C)).
Checking FairEG (Explicit-State)
SCC-based Check_FairEG (cont.)
Check_FairEG([φ]):
(i) restrict the graph of M to [φ];
(ii) find all fair non-trivial SCCs C i
(iii) build C := ∪ i C i ;
(iv) compute the states that can reach C (Check_EU([φ],C)).
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Check_FairEG(¬C 1 ): 1. compute [¬C 1 ]
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Check_FairEG(¬C 1 ): 2. restrict the graph to [¬C 1 ]
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Check_FairEG(¬C 1 ): 3. find all fair non-trivial SCC’s
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Check_FairEG(¬C 1 ): 4. build the union C of all SCC’s
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Check_FairEG(¬C 1 ): 5. compute the states which can reach it
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Check_FairEU(>, ϕ) = Check_EU(>, ϕ ∧ fair )
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
fair=Check_FairEG(>)
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Check_FairEU(>, ϕ) = Check_EU(>, ϕ ∧ fair )
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Checking FairEG (Explicit-State)
Example: Check_FairEG
F := {{ not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
=⇒ Property Verified
Checking FairEG (Explicit-State)
SCC-based Check_FairEG - Drawbacks
SCCs computation requires a linear (O(#nodes + #edges) ) DFS (Tarjan).
The DFS manipulates the states explicitly, storing information for every state.
A DFS is not suitable for symbolic model checking where we manipulate sets of states.
We want an algorithm based on the preimage computation.
Checking FairEG (Explicit-State)
SCC-based Check_FairEG - Drawbacks
SCCs computation requires a linear (O(#nodes + #edges) ) DFS (Tarjan).
The DFS manipulates the states explicitly, storing information for every state.
A DFS is not suitable for symbolic model checking where we manipulate sets of states.
We want an algorithm based on the preimage computation.
Checking FairEG (Explicit-State)
SCC-based Check_FairEG - Drawbacks
SCCs computation requires a linear (O(#nodes + #edges) ) DFS (Tarjan).
The DFS manipulates the states explicitly, storing information for every state.
A DFS is not suitable for symbolic model checking where we manipulate sets of states.
We want an algorithm based on the preimage computation.
Checking FairEG (Explicit-State)
SCC-based Check_FairEG - Drawbacks
SCCs computation requires a linear (O(#nodes + #edges) ) DFS (Tarjan).
The DFS manipulates the states explicitly, storing information for every state.
A DFS is not suitable for symbolic model checking where we manipulate sets of states.
We want an algorithm based on the preimage computation.
Checking FairEG (Symbolic)
Outline
1 Fair CTL Model Checking: Generalities
2 Checking Fair EG (Explicit-State)
3 Checking Fair EG (Symbolic)
Checking FairEG (Symbolic)
Emerson-Lei Algorithm
Recall the fixpoint characterization of EG:
[EGφ] = νZ .([φ] ∩ [EXZ ])
The greatest set Z s.t. every state z in Z satisfies φ and reaches another state in Z in one step.
We can characterize E f G similarly:
[E f Gφ] = νZ .([φ] ∩ T
F
i∈FT [EX E(Z U(Z ∩ F i ))])
The greatest set Z s.t. every state z in Z satisfies φ and, for every set F i ∈ FT, z reaches a state in F i ∩ Z by means of a non-trivial path that lies in Z.
[EG ] φ
Z [φ]
Checking FairEG (Symbolic)
Emerson-Lei Algorithm
Recall the fixpoint characterization of EG:
[EGφ] = νZ .([φ] ∩ [EXZ ])
The greatest set Z s.t. every state z in Z satisfies φ and reaches another state in Z in one step.
We can characterize E f G similarly:
[E f Gφ] = νZ .([φ] ∩ T
F
i∈FT [EX E(Z U(Z ∩ F i ))])
The greatest set Z s.t. every state z in Z satisfies φ and, for every set F i ∈ FT, z reaches a state in F i ∩ Z by means of a non-trivial path that lies in Z.
[EG ] φ
Z [φ]
[E G ]
fφ
F1 F2
Fn
Z
F3
[φ]
Checking FairEG (Symbolic)
Emerson-Lei Algorithm
Recall: [E f Gφ] = νZ .([φ] ∩ T
F
i∈FT [EX E(Z U(Z ∩ F i ))]) state_set Check_FairEG( state_set [φ]) {
Z’:= [φ];
repeat Z:= Z’;
for each Fi in FT
Y:= Check_EU(Z,Fi∩Z);
Z’:= Z’ ∩ PreImage(Y));
end for;
until (Z’ = Z);
return Z;
}
Implementation of the above formula
Checking FairEG (Symbolic)
Emerson-Lei Algorithm
Recall: [E f Gφ] = νZ .([φ] ∩ T
F
i∈FT [EX E(Z U(Z ∩ F i ))]) state_set Check_FairEG( state_set [φ]) {
Z’:= [φ];
repeat Z:= Z’;
for each Fi in FT
Y:= Check_EU(Z’,Fi∩Z’);
Z’:= Z’ ∩ PreImage(Y));
end for;
until (Z’ = Z);
return Z;
}
Slight improvement: do not consider states in Z \ Z 0
Checking FairEG (Symbolic)
Emerson-Lei Algorithm (symbolic version)
Recall: [E f Gφ] = νZ .([φ] ∩ T
F
i∈FT [EX E(Z U(Z ∧ F i ))]) Obdd Check_FairEG( Obdd φ) {
Z’:= φ;
repeat Z:= Z’;
for each Fi in FT
Y:= Check_EU(Z’,Fi∧Z’);
Z’:= Z’ ∧ PreImage(Y));
end for;
until (Z’ ↔ Z);
return Z;
}
Symbolic version.
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
EGg = νZ .g ∧ EXZ
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
EGg = νZ .g ∧ EXZ
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
EGg = νZ .g ∧ EXZ
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
EFg = E(>Ug) = µZ .g ∨ (> ∧ EXZ ) = µZ .g ∨ EXZ
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
EFg = E(>Ug) = µZ .g ∨ (> ∧ EXZ ) = µZ .g ∨ EXZ
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
EFg = E(>Ug) = µZ .g ∨ (> ∧ EXZ ) = µZ .g ∨ EXZ
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
EFg = E(>Ug) = µZ .g ∨ (> ∧ EXZ ) = µZ .g ∨ EXZ
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
EFg = E(>Ug) = µZ .g ∨ (> ∧ EXZ ) = µZ .g ∨ EXZ
Checking FairEG (Symbolic)
Example: normal Check_EG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= AG(T 1 → AFC 1 ) = ¬EF(T 1 ∧ EG¬C 1 )
=⇒ Property not verified
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
E f Gg = νZ .g ∧ EXE(Z U(Z ∧ F 1 )) ∧ EXE(Z U(Z ∧ F 2 ))
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
E f Gg = νZ .g ∧ EXE(Z U(Z ∧ F 1 )) ∧ EXE(Z U(Z ∧ F 2 ))
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
E f Gg = νZ .g ∧ EXE(Z U(Z ∧ F 1 )) ∧ EXE(Z U(Z ∧ F 2 ))
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
E f Gg = νZ .g ∧ EXE(Z U(Z ∧ F 1 )) ∧ EXE(Z U(Z ∧ F 2 ))
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
E f Gg = νZ .g ∧ EXE(Z U(Z ∧ F 1 )) ∧ EXE(Z U(Z ∧ F 2 ))
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Fixpoint reached
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2
M |= A f G(T 1 → A f FC 1 ) = ¬E f F(T 1 ∧ E f G¬C 1 )
Checking FairEG (Symbolic)
Example: Check_FairEG
F := { { not C1},{not C2}}
turn=1
turn=2
turn=2 turn=2
turn=1 turn=1
turn=1
turn=2
T1, C2 N1, C2 T1, T2
T1, T2
N1, T2
C1, T2 C1, N2
T1, N2
N1, N2 turn=0
not C1 not C2