User manual/mcrl22lps

From MCRL2

< User manual

Jump to: navigation, search

User manual

Tool manual pages

Contents

Translate an mCRL2 specification to a linear process specification (LPS).

1 Synopsis
2 Short description
3 Options
4 Author
5 Bug reporting

Synopsis

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

Short description

The tool mcrl22lps translates an mCRL2 process specification to a linear process specification (LPS). The input is read from INFILE and the output is written to OUTFILE. If OUTFILE is not present, stdout is used. If INFILE is not present, stdin is used.

The input process specification should adhere to its syntax description (see also the language reference 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 a 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.

Options

OPTION can be any of the following:

-a, --statenames: Using this option, the names of generated data parameters are extended with the name of the process in which they occur. In this way it is easier to determine where the parameter comes from.

-b, --binary: This option causes all generated finite sorts to be encoded using boolean. These finite sorts are generated when clustering and when generating state variables. See --cluster and --newstate.

-c, --cluster: This option causes the output linear process to be clustered. This option is not used by default. Clustering means that summands with the same action labels are taken together. For instance, a(f₁)·P(g₁) + a(f₂)·P(g₂) is replaced by ∑_b:Bool a(if(b,f₁,f₂))·P(if(b,g₁,g₂)). The advantage is that the number of summands can be reduced substantially 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 --binary can be used which causes all new sorts to be encoded using booleans.

-D, --delta: With this option a (untimed) delta summand is added to each state of each process. This influences the behaviour of timed processes in the sense that processes can also choose to idle, without being forced to perform an action. For untimed processes this was already the case, and there is no effect on the semantics. The advantage of this option is that the delta can subsume all other conditional and timed delta's reducing the number of delta summands in the resulting linear process. Furthermore, as processing delta summands can be very time consuming, this option can make linearisation substantially faster.

-e, --check-only: Using this option mcrl22lps only checks the syntax and the static semantics of the input, but it will not execute the linearisation process. This is useful to check whether the input is proper mCRL2.

-f, --no-globvars: When linearising, there are several places where the values of data variables are irrelevant for the behaviour of the process. E.g. when linearising the process X = ∑_d:D read(d)·send(d)·X, the value of the variable d has no meaning after the send action. In this case a 'global variable' is introduced to indicate that the value of this variable can be chosen freely. As the number of global variables can become quite large, the generation of such variables can be avoided by using this option. In this case a dummy value is chosen, which is the same for each sort.

-g, --no-deltaelm: With this option the linearisation will not attempt to remove 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.

-lNAME, --lin-method=NAME

Use linearisation method NAME:

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.

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, P₁(f(x)) · P₂(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) = P₁(f(x)) · P₂(g(x)). With the regular2 method a variable is introduced for every term. In this latter case P is defined by P(y,z) = P₁(y) · P₂(z) and the expression P₁(f(x)) · P₂(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)·δ. Now with regular infinitely many new processes are generated, each of the following form: P(0)·δ, P(1)·δ, etc. With regular2 only one new process is generated, namely one for P(n)·δ.

The regular method is used by default.

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.

-m, --no-sumelm: This option causes the linearisation to avoid sum elimination. If there is a condition or part of a condition of the form x = t with x a variable bound in a sum operator, then the term t can often be substituted for x, and the sum over x can be removed. Sometimes searching for equations x = t can be very time consuming. Using the flag --no-sumelm sum elimination can be switched off.

-n, --no-cluster: This option prevents clustering of linear processes 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 --cluster, esp. for a short explanation of the clustering process.

-o, --no-rewrite: This option prevents intermediate rewriting of terms. This is especially useful when the equations in the input specification are not terminating, as in this case the lineariser will not terminate.

-rNAME, --rewriter=NAME: Use rewrite strategy NAME. mcrl22lps simplifies data expressions using the

rewriter. To prevent rewriting the option -o, --no-rewrite can be used.

-w, --newstate: The sort of state variables is by default Pos, i.e. positive natural numbers. 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.

-z, --no-alpha: 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.

Standard options: