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:

  1. place this file under the rules/ directory in the TLV installation and add it at the end of rules/Rules.tlv, so it is autoloaded,
  2. for each example file foo.smv, there is a foo.pf file. 
  3. run “tlv foo.smv”; and do the commands “Load foo.pf;”  and “doit;” on the TLV command line

 

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:

  1. mutex.smv (the mutex example from the paper),  mutex.pf

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

 

  1. mutex+.smv (the mutex example, with an auxiliary variable), mutex+.pf

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

 

  1. szymanski.smv, szymanski.pf

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

 

  1. enter-pme+.smv (enter-pme.smv with auxiliary variables denoting the existence of processes in certain states.), enter-pme+.pf

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