Given an LPS:

\[\begin{split}\begin{array}{lll}
P(d:D) &=& \ldots + \sum_{e_i:E_i} c_i(d,e_i) \to a_i(f_i(d,e_i)) \cdot P(g_i(d,e_i)) +\\
&& \ldots + \sum_{e_j:E_j} c_j(d,e_j) \to \tau \cdot P(g_j(d,e_j)) + \ldots
\end{array}\end{split}\]

\(tau\)-summand \(j\) is confluent with summand \(i\) if the following condition holds:

\[\begin{split}\begin{array}{l}
\forall d{:}D.\forall e_i{:}E_i. \forall e_j{:}E_j . (inv(d) \land c_i(d,e_i) \land c_j(d,e_j)) \Rightarrow\\
(c_i(g_j(d,e_j),e_i) \land c_j(g_i(d,e_i),e_j) \land\\
f_i(d,e_i) = f_i(g_j(d,e_j),e_i) \land g_i(g_j(d,e_j),e_i) = g_j(g_i(d,e_i),e_j))
\end{array}\end{split}\]

where \(inv\) is the invariant specified using the option –invariant. In case \(a_i\) is also a \(tau\)-action, this formula can be weakened to the following:

\[\begin{split}\begin{array}{l}
\forall d{:}D. \forall e_i{:}E_i. \forall e_j{:}E_j . (inv(d) \land c_i(d,e_i) \land c_j(d,e_j)) \Rightarrow\\
(g_i(d,e_i) = g_j(d,e_j) \lor (c_i(g_j(d,e_j),e_i) \land c_j(g_i(d, e_i),e_j) \land\\
g_i(g_j(d,e_j),e_i) = g_j(g_i(d,e_i),e_j)))
\end{array}\end{split}\]

If the option :option`–invariant` is not used, the invariant is equal to
`true`

.

The tool will generate these confluence conditions for all \(tau\)-summands and tries to prove that they are tautologies using a BDD based prover for propositional formulas. In some cases lpsconfcheck indicates that a \(tau\)-summand is not confluent even though it is. The option –verbose gives insight into what the prover is doing and can be used to see if rewrite rules have to be added to the specification in order to enable the prover to determine that certain condition are indeed tautologies.

In some cases it may be useful to use an SMT solver to assist the prover. The SMT solver can further reduce BDDs by removing inconsistent paths. A specific SMT solver can be chosen using the option –smt-solver=SOLVER`. Either the SMT solver Ario or CVC3 can be used. To use one of these solvers, the directory containing the corresponding executable must be in the path.

The tool can determine whether two summands are confluent in three ways and will indicate which of the methods was used while proving confluence. The three ways of determining confluence are as follows:

If summand number 1 has been proven confluent with summand number 2, summand number 2 is also confluent with summand number 1. This method of checking confluence is called checking confluence by symmetry. If two summands are confluent by symmetry, lpsconfcheck indicates this by printing a dot (‘.’).

Another way of checking the confluence of two summands is determining whether the two summands are syntactically disjoint. Two summands are syntactically disjoint if the following holds:

The set of variables used by one summand is disjoint from the set of variables changed by the other summand and vice versa.

The set of variables changed by one summand is disjoint from the set of variables changed by the other summand.

If two summands are confluent because of syntactic disjointness, lpsconfcheck indicates this by printing a colon (‘:’).

The most time consuming way of checking the confluence of two summands is generating the confluence condition and then checking if this condition is a tautology using the prover. If two summands are proven confluent using the prover, lpsconfcheck indicates this by printing a plus sign (‘+’). If the option –generate-invariants is used, the tool will try to prove that the reduced confluence condition is an invariant of the LPS, in case the confluence condition is not a tautology. If the reduced confluence condition is indeed an invariant, the two summands are proven confluent lpsconfcheck indicates this by printing an ‘i’.

If there already is an action named ‘’ctau’’ present in the LPS as found in ‘’INFILE’’, an error will be reported.

```
lpsconfcheck [OPTION]... [INFILE [OUTFILE]]
```

Checks which tau-summands of the mCRL2 LPS in INFILE are confluent, marks them by renaming them to ctau, and write the result to OUTFILE. If INFILE is not present stdin is used. If OUTFILE is not present, stdout is used.

`-a`

, `--check-all`

check the confluence of tau-summands regarding all other summands, instead of continuing with the next tau-summand as soon as a summand is encountered that is not confluent with the current tau-summand

`-x[CONDITIONS]`

, `--conditions[CONDITIONS]`

use the confluence conditions specified by individual characters (c/C: commutative confluence with/without disjointness check; d: commutative confluence with disjointness check only; T: triangular confluence; Z: trivial confluence)

`-c`

, `--counter-example`

display a valuation for which the confluence condition does not hold, in case the encountered condition is neither a contradiction nor a tautolgy

`-g`

, `--generate-invariants`

try to prove that the reduced confluence condition is an invariant of the LPS, in case the confluence condition is not a tautology

`-o`

, `--induction`

apply induction on lists

`-iINVFILE`

, `--invariantINVFILE`

use the boolean formula (an mCRL2 data expression of sort Bool) in INVFILE as invariant

`-n`

, `--no-check`

do not check if the invariant holds before checking for for confluence

`-m`

, `--no-marking`

do not mark the confluent tau-summands; since there are no changes made to the LPS, nothing is written to OUTFILE

`-u`

, `--no-sums`

do not rewrite summands with a sum operator and prove their confluence formula

`-pPREFIX`

, `--print-dotPREFIX`

save a .dot file of the resulting BDD in case two summands cannot be proven confluent; PREFIX will be used as prefix of the output files

`-QNUM`

, `--qlimitNUM`

limit enumeration of quantifiers to NUM iterations. (Default NUM=1000, NUM=0 for unlimited).

`-rNAME`

, `--rewriterNAME`

use rewrite strategy NAME:

`jitty`

jitty rewriting

`jittyc`

compiled jitty rewriting

`-zSOLVER`

, `--smt-solverSOLVER`

use SOLVER to remove inconsistent paths from the internally used BDDs (by default, no path elimination is applied):

`cvc`

the SMT solver CVC3

`z3`

the SMT solver Z3

`-sNUM`

, `--summandNUM`

eliminate or simplify the summand with number NUM only

`-tLIMIT`

, `--time-limitLIMIT`

spend at most LIMIT seconds on proving a single formula

`--timings[FILE]`

append timing measurements to FILE. Measurements are written to standard error if no FILE is provided

`-q`

, `--quiet`

do not display warning messages

`-v`

, `--verbose`

display short intermediate messages

`-d`

, `--debug`

display detailed intermediate messages

`--log-levelLEVEL`

display intermediate messages up to and including level

`-h`

, `--help`

display help information

`--version`

display version information

Luc Engelen