This web page describes experiments on split invariance with the TLV tool. The split invariance calculator is contained in the file split-invariance.tlv.
To run the calculations in TLV:
The output for each example includes a representative, theta(1), or theta(1,2) as the case may be.
The instance size was calculated with the formula from the paper on IIV in CAV 2005. This is: N = max(E_theta+A_phi, E_rho+A_phi + E_phi, A_phi+A_p), where E_x and A_x refer to the number of existentially/ universally quantified variables in a formula x; and theta is the initial condition, phi is the candidate invariant, rho is the transition relation, and p is the correctness formula.
In all cases below, E_theta, E_phi are 0, so the formula simplifies to A_phi + max(E_rho, A_p).
Programs:
theta(1,2): (x = 1 -> P[1].loc in {0,1} & P[2].loc != 2) & (x = 0 -> (P[1].loc = 2 -> P[2].loc != 2));
A_phi = 2, E_rho = 0, A_p = 2
theta(1): (x = 1 -> P[1].loc != 2) & (x = 0 ->
(last = 2 -> P[1].loc != 2) & (last = 1 -> P[1].loc = 2));
(here, last=2 should be interpreted as last!=1)
A_phi = 1, E_rho=0, A_p = 2
theta(1,2): (loc[1] in {6,7} -> loc[2] in {0,1,5,6}) & (loc[1] = 5 -> loc[2] notin {7,2}) & (loc[1] in {3,4} -> loc[2] notin {7,6}) & (loc[1] = 2 -> loc[2] notin {7,6,5});
A_phi = 2, E_rho=2,A_p=2
the resulting theta(1) [big!].
A_phi=1, E_rho=2,A_p=0
Results table
|
program |
Invariant type |
Computation time |
Instance size |
Size of theta(1) or theta(1,2) (in bytes) |
Total BDD nodes |
|
mutex |
2-universal |
0.01 seconds |
4 |
9 |
1327 |
|
Mutex+ |
1-universal |
0.01 |
3 |
8 |
1007 |
|
Szymanski |
2-universal |
0.03 |
4 |
18 |
9956 |
|
Enter-pme+ |
1-universal |
1.66 seconds |
3 |
2793 |
353220 |