pbes2booldeprecated

Generation of a BES

The tool uses the algorithm from pbes2bes for generating a BES in case the input file is a PBES.

Note

Also see pbes2bes for a description of the strategies that are referred to in this tool description.

Solving a BES

After the BES is generated, it can be solved. For this a backward approximation technique is followed. First all instantiated BES variables of the highest alternation depth are calculated. The variables are all simultaneously set to true or false depending on the fixpoint symbol at this depth. By a normal fixpoint iteration, a stable solution is calculated. This process must be symbolic, as variables at lower alternation depths can still occur in the approximation.

The results of this approximation are substituted in all equations of lower alternation depth, just as in Gauss-elimination. In a sense this is the ordinary Gauss elimination process, except that it treats all variables at the same alternation depth at once. For instance when the alternation depth is 0, i.e. there is no alternation, this approximation process converges in linear time. For arbitrary nesting depths, this procedure is exponential.

Generation of counter examples

It is possible to let pbes2booldeprecated generate a counter example. As it stands, counterexamples are most useful when generated with strategy 2. A counterexample is a tree with the initial instantiated pbes variable as its root. The branches of each node are printed as lines with two extra spaces of indentation. These branches are labelled with instantiated pbes variables of which the value determined the value of our node. Typically a counter example looks like:

Solving the BES with 10 equations.
The pbes is not valid
Below the justification for this outcome is listed
1: X(0)
  2: Subst:false X(2)
    4: Subst:false X(5)
  3: Subst:false X(9)

This says that when solving X(0), it could be determined that it had solution false, because X(2) and X(9) where also false. The instantiated variable X(2) was false because X(5) was false. Apparently, X(5) and X(9) where invalid by itself.

The phrase Subst:false indicates the reason why a substitution was made. The following indications exist:

Mu Cycle

the variable is set to false because it is part of a cycle in a class of variables that all have the same alternation depth, and are preceded by a mu (strategy 3).

Nu Cycle

as in a Mu Cycle, except that the variable is set to true and the variables are preceded by nu (strategy 3).

Subst:false

false is substituted using back or forward substitution (strategy 2).

Subst:true

the value true is substituted using back or forward substitution (strategy 2).

FSubst:false

the value false is substituted by forward substition (strategy 1).

FSubst:true

the value true is substituted by backward substitution (strategy 1).

Set:false

variable is set to false (currently not used).

Set:true

variable is set to true (currently not used).

Appr:false

false is substitued for the variable when solving it using approximation.

Appr:true

true is substituted for the variable when solving it using approximation.

Approxim

a value not equal to true or false is substituted when solving the BES using approximation.

Sometimes the counterexample is recursive, or has re-occuring parts. these parts are only given once in the counterexample. A * at the end of a line in the counterexample indicates that this instantiated variable did already occur earlier in the counterexample and therefore, the reasons why it is true or false are not printed again.

Known issues

The counter example generated when the approximation algorithm of boolean equations is being used is in general huge and not very helpful. This algorithm is always employed with strategies 0 and 1. With strategies 2 and 3 it can be that when generating the boolean equation system from a PBES, it is already detected that the initial instantiated variable is either true or false and the approximation algorithm is not necessary. Counter examples in this case are compact (although we have no proof that the counter examples are always optimal) and also very helpful.