# mcrl22lps

This translates an mCRL2 process specification to a linear process specification (LPS).

The input process specification should adhere to its syntax description (see also mCRL2 specification for more information).

The process in the input must be in parallel pCRL format. This means that it must consist of the parallel composition of a set of processes that are described using actions, conditions, sum operators, timing, sequential and alternative composition operators only. The parallel, communication and renaming operators can only be used on the outer level. Typical input examples are found in the directory examples of the mCRL2 repository.

For certain inputs, mcrl22lps can take a large amount of time. In some cases it will not terminate, for instance with non terminating rewrite rules. The following options can be used to speed up the linearisation, at the expense of a less readable result.

The option –lin-method=stack avoids non termination if the process structure is not regular. The option –no-rewrite causes rewriting to be switched off, avoiding non termination due to non terminating rewrite rules. The option –no-sumelm avoids the use of sum elimination, which under certain circumstances may take a lot of time. Finally, the option –no-deltaelm avoids removal of spurious delta summands, which uses a quadratic algorithm in the number of summands, and therefore, may be very time consuming.

The option –timed assumes that the timing of the input is strict. By
default it is assumed that time can always progress in the sense that each
process `p`

is interpreted as `p+delta`

, which is incorrect as it does not
preserve time. For instance the process `a@1`

is interpreted as `a@1+delta`

,
meaning that the `a`

does not have to happen at time `1`

. If time is
important, the option –timed is required. However, this may lead to
substantially increased linearisation times and an increased size of the linear
process.

## Linearisation methods

The tool supports three different linearisation methods, configurable using the option -l/–lin-method:

`regular`

The non parallel processes are translated to restricted Greibach Normal Form. Instead of using a stack, these processes are translated to an LPS with finite control variables. If some process has an infinite number of control states, the tool will attempt to generate all of them, causing it to run out of memory. In such a case the stack method can be used to produce a linear process. The regular method is almost the same as

`regular2`

. The only difference is in the way new process variables are generated:`regular`

generates less parameters in the linear process than`regular2`

, but`regular2`

generates an LPS in a few cases where the use of regular leads to non-termination. The difference between the two methods is explained best by an example.The tool sometimes has to replace a sequence of process variables by a single new variable. For instance,

`P1(f(x)) · P2(g(x))`

must be replaced by a new process`P`

. With the`regular`

method, the new process has a single parameter`x`

, matching the single free variable`x`

. I.e. the definition of`P`

is`P(x) = P1(f(x)) · P2(g(x))`

. With the`regular2`

method a variable is introduced for every term. In this latter case,`P`

is defined by`P(y,z) = P1(y) · P2(z)`

and the expression`P1(f(x)) · P2(g(x))`

is replaced by`P(f(x),g(x))`

.We give an example in which linearisation with

`regular`

fails to terminate and the use of`regular2`

succeeds. Consider the process definition`P(n:Nat) = a·P(n+1) + b`

and let the initial process be`P(0)·delta`

. Now with regular infinitely many new processes are generated, each of the following form:`P(0)·delta`

,`P(1)·delta`

, etc. With`regular2`

only one new process is generated, namely one for`P(n)·delta`

.

`regular2`

See the explanation of regular. Note that with this option the number of parameters can be very large, and consequently, the number of global variables can be huge too. In this case, linearising using the option -f/–no-globvars is advisable.

`stack`

The LPS is generated using stack data types. The non parallel processes are transformed to restricted Greibach Normal Form and straightforwardly translated to linear processes using a stack. The resulting linear processes are then put in parallel. This works for any allowed input. Unfortunately, the linear process that is the result of this operation can basically only be used for state space generation. Symbolic operations on the stacks are generally not very effective, because the stack data type is too complex. For symbolic analysis, linearisation methods

`regular`

or`regular2`

can be used.

- orphan:

### Usage

```
mcrl22lps [OPTION]... [INFILE [OUTFILE]]
```

### Description

Linearises the mCRL2 specification in INFILE and writes the resulting LPS to OUTFILE. If OUTFILE is not present, stdout is used. If INFILE is not present, stdin is used.

### Command line options

`--balance-summands`

transform inputs expressions p1 + … + pn into a balanced tree before linearising. Sometimes helpful in preventing stack overflow.

`-b`

, `--binary`

when clustering use binary case functions instead of n-ary; in the presence of -w/–newstate, state variables are encoded by a vector of boolean variables

`-e`

, `--check-only`

check syntax and static semantics; do not linearise

`-c`

, `--cluster`

all actions in the final LPS are clustered. Clustering means that summands with the same action labels are grouped together. For instance, a(f1) . P(g1) + a(f2) . P(g2) is replaced by sum b: Bool . a(if(b, f1, f2)) . P(if(b, f2, g2)). The advantage is that the number of summands can be reduced subtantially in this way. The disadvantage is that sum operators are introduced and new data sorts with auxiliary functions are generated. In order to avoid the generation of new sorts, the option -b/–binary can be used.

`-D`

, `--delta`

add a true->delta summands to each state in each process; these delta’s subsume all other conditional timed delta’s, effectively reducing the number of delta summands drastically in the resulting linear process; speeds up linearisation. This is the default, but it does not deal correctly with time.

`-lNAME`

, `--lin-method=NAME`

use linearisation method NAME:

`regular`

for generating an LPS in regular form (specification should be regular)

`regular2`

for a variant of ‘regular’ that uses more data variables (useful when ‘regular’ does not work)

`stack`

for using stack data types (useful when ‘regular’ and ‘regular2’ do not work)

`-w`

, `--newstate`

state variables are encoded using enumerated types instead of positive natural numbers (Pos). By using this option new finite sorts named Enumk are generated where k is the size of the domain. Also, auxiliary case functions and equalities are defined. In combination with the option –binary the finite sorts are encoded by booleans. (requires linearisation method ‘regular’ or ‘regular2’).

`-z`

, `--no-alpha`

alphabet reductions are not applied. By default mcrl22lps attempts to distribute communication, hiding and allow operators over the parallel composition operator as this reduces the size of intermediate linear processes. By using this option, this step can be avoided. The name stems from the alphabet axioms in process algebra.

`-n`

, `--no-cluster`

the actions in intermediate LPSs are not clustered before they are put in parallel. By default these processes are clustered to avoid a blow-up in the number of summands when transforming two parallel linear processes into a single linear process. If a linear process with M summands is put in parallel with a linear process with N summands the resulting process has M×N + M + N summands. Both M and N can be substantially reduced by clustering at the cost of introducing new sorts and functions. See -c/–cluster, esp. for a short explanation of the clustering process.

`--no-constelm`

do not try to apply constant elimination when generating a linear process.

`-g`

, `--no-deltaelm`

avoid removing spurious delta summands. Due to the existence of time, delta summands cannot be omitted. Due to the presence of multi-actions the number of summands can be huge. The algorithm for removing delta summands simply works by comparing each delta summand with each other summand to see whether the condition of the one implies the condition of the other. Clearly, this has quadratic complexity, and can take a long time.

`-f`

, `--no-globvars`

instantiate don’t care values with arbitrary constants, instead of modelling them by global variables. This has no effecton global variables that are declared in the specification.

`-o`

, `--no-rewrite`

do not rewrite data terms while linearising; useful when the rewrite system does not terminate. This option also switches off the application of constant elimination.

`-m`

, `--no-sumelm`

avoid applying sum elimination in parallel composition

`-QNUM`

, `--qlimit=NUM`

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

`-rNAME`

, `--rewriter=NAME`

use rewrite strategy NAME:

`jitty`

jitty rewriting

`jittyc`

compiled jitty rewriting

`jittyp`

jitty rewriting with prover

`-a`

, `--statenames`

the name of the variable encoding the state of a parallel process has the shape “si”, with i an optional number. Using this flag this name is “Pi”, where P is the nameof the process. This makes it easier to determine to which process the state variable belongs from.

`-T`

, `--timed`

Translate the process to linear form preserving all timed information. In parallel processes the number of possible time constraints can be large, slowing down linearisation. Confer the –delta option which yiels a much faster translation that does not preserve timing correctly

`--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