pbesparelm

The purpose of this tool is to find those parameters in parameterised Boolean equation sytems that do not affect the solution, and remove those in a similar fashion as lpsparelm.

Example:

$\begin{array}{l} \nu V(n{:}\mathbb{N}, b{:}\mathbb{B}) = (b \Rightarrow V(n + 1, b)) \land W(n, b)\\ \mu W(n{:}\mathbb{N}, b{:}\mathbb{B}) = b \lor (b \land W(n+1, b))\\ ~\\ \mathbf{init}\ V(0,\mathit{true}) \end{array}$

Instantiation of this PBES using tools such as pbes2bool or pbessolve does not terminate. However, in this PBES, parameter $n$ of both equations is redundant (it does not appear positively in any equation), and can be removed. The resulting PBES will be:

$\begin{array}{l} \nu V(b{:}\mathbb{B}) = (b \Rightarrow V(b)) \land W(b)\\ \mu W(b{:}\mathbb{B}) = b \lor (b \land W(b))\\ ~\\ \mathbf{init}\ V(0,\mathit{true}) \end{array}$

The algorithm underlying the tool is described in detail in [OWW09].

The tool can also be applied to parameterised Boolean equation systems that contain counter example information. The result can subsequently be solved with pbessolve, using the following approach. Consider the PBES below where the counter example information is encoded by the $Z$ -variables:

$\begin{array}{l} \nu Y(n{:}\mathbb{B}) = (Y(\neg n) \land Zpos_{a}(n, n, \neg n)) \lor Zneg_{a}(n, n, \neg n)\\ \nu Zpos_{a}(n, v, n'{:}\mathbb{B}) = \mathit{true}\\ \mu Zneg_{a}(n, v, n'{:}\mathbb{B}) = \mathit{false}\\ ~\\ \mathbf{init}\ Y(\mathit{true}) \end{array}$

The $Z$ -variables and their equations must be preserved for counter example generation. Therefore, we remove the redundant parameter $n$ in two steps:

pbesrewr --pbes-rewriter=remove-cex-variables original.pbes core.pbes
pbesparelm --ignore-cex core.pbes parelmcore.pbes

In the first step we obtain the core of the PBES as defined in [SKLW25]. The result of the second step is the PBES shown below.

$\begin{array}{l} \nu Y = Y\\ \nu Zpos_{a}(n, v, n'{:}\mathbb{B}) = \mathit{true}\\ \mu Zneg_{a}(n, v, n'{:}\mathbb{B}) = \mathit{false}\\ ~\\ \mathbf{init}\ Y \end{array}$

We can now provide the two equation systems to pbessolve and save some computation effort while preserving the solution and the counter example of the original PBES. As usual, we must also provide the LPS from which the original PBES was constructed. The command is as follows:

pbessolve parelmcore.pbes --original-pbes=original.pbes -f original.lps

Usage

pbesparelm   [OPTION]... [INFILE [OUTFILE]]

Description

Reads a file containing a PBES, and applies parameter elimination to it. If OUTFILE is not present, standard output is used. If INFILE is not present, standard input is used.

Command line options

--ignore-cex

Ignores the counter example equations if present.

-iFORMAT , --in=FORMAT

use input format FORMAT:

pbes

PBES in internal format

pgsolver

BES in PGSolver format

text

PBES in textual (mCRL2) format

-oFORMAT , --out=FORMAT

use output format FORMAT:

bes

BES in internal format

pbes

PBES in internal format

pgsolver

BES in PGSolver format

text

PBES in textual (mCRL2) format

--timings[=FILE]

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

Standard options

-q , --quiet

do not display warning messages

-v , --verbose

display short log messages

-d , --debug

display detailed log messages

--log-level=LEVEL

display log messages up to and including level; either warn, verbose, debug or trace

-h , --help

display help information

--version

display version information

--help-all

display help information, including hidden and experimental options

Author

Wieger Wesselink; Simon Janssen and Tim Willemse