Linearize (merge)

This CIF to CIF transformation performs process-algebraic linearization, thereby eliminating parallel composition, event synchronization and channel communication.

This transformation eliminates non-determinism, resulting in specifications with smaller state spaces, at the expense of not preserving the specification’s full behavior. To maintain non-determinism, preserving the specification’s full behavior, at the expensive of a possible exponential blow-up of the specification in terms of number of edges, use the linearize (product) CIF to CIF transformation instead.

Supported specifications

This transformation supports a subset of CIF specifications. The following restrictions apply:

  • Specifications without automata are not supported.

Preprocessing

The following CIF to CIF transformations are applied as preprocessing (in the given order), to increase the subset of CIF specifications that can be transformed:

Implementation details

A location pointer variable is introduced for each original automaton with at least two locations, and the use of locations in expressions is eliminated. This is mostly similar to what the Eliminate the use of locations in expressions CIF to CIF transformation does, except that for instance location pointer variables are added for all automata with at least two locations.

One new automaton, named M, is created. If all original automata have the same supervisory kind, the new automaton gets this kind as well. Otherwise, it gets no supervisory kind. The alphabet of this new automaton is the union of alphabets of the original automata, including the events that are used to send or receive in any of the automata.

The structure of the original model is kept intact as much as possible, to allow objects to retain their absolute identities (absolute names). Since all automata are linearized into a single automaton, the original automata are replaced by groups. Each replacement group will contain (as much as possible) all of the declarations, invariants, etc of its original automaton.

All discrete and continuous variables from the original automata are moved to the new automaton, to ensure they can be assigned by the new automaton. Discrete variables must be moved to the single new automaton as they can only be declared in automata. All continuous variables of the original automata are moved to the single new automaton, regardless of whether they are assigned by updates on edges or not. Continuous variables declared outside automata remain where they are. The moved discrete and continuous variables are renamed based on their absolute names. That is, for an automaton a with a discrete variable v, the absolute name of the constant is a.v and the moved variable will be named a_v.

One location, named L, is added to the new automaton. This location is both initial and marked.

All initialization and marker predicates from the locations of the original automata are merged together. They are each put in the group that replaces their respective original automaton. Similarly, the invariants of the locations of the original automata are also each moved to their corresponding groups. And the initialization and marker predicates specified in automata, as well as invariants specified in automata, are moved there as well.

For the tau event, a self loop is created per original tau edge. For all other events, the edges are merged, resulting in a single self loop for each non-tau event. By creating single edges per non-tau event, non-deterministic choice may be eliminated, ensuring that the model size of the resulting specification is near-linear compared to the model size of the original specification.

Monitors are taken into account when merging the guards of the edges, resulting in simpler guard predicates. Communication is eliminated altogether, and events no longer have data types after linearization. For edges with receives, the 'received value' is replaced (in the updates) by the 'send value'.

For instance, the following specification:

event e;

plant automaton p:
  disc int x = 1;

  location l1:
    initial;
    edge e when x = 1 do x := 2 goto l2;

  location l2:
    edge e when x = 2 do x := 1 goto l1;
end

plant automaton q:
  location l1:
    initial;
    edge tau goto l2;

  location l2:
    edge e goto l1;
end

is transformed to the following specification:

event e;

group p:
  enum LPE = l1, l2;

  initial M.p = l1 and true or M.p = l2 and false;
  marked M.p = l1 and false or M.p = l2 and false;
end

group q:
  enum LPE = l1, l2;

  initial M.q = l1 and true or M.q = l2 and false;
  marked M.q = l1 and false or M.q = l2 and false;
end

plant automaton M:
  alphabet e;

  disc int p_x = 1;
  disc .p.LPE p = .p.l1;
  disc .q.LPE q = .q.l1;

  location L:
    initial;
    marked;

    edge e when (p = .p.l1 and p_x = 1 or p = .p.l2 and p_x = 2) and
                (q = .q.l1 and false or q = .q.l2 and true)
           do if p = .p.l1 and p_x = 1: p_x := 2, p := .p.l2
              elif p = .p.l2 and p_x = 2: p_x := 1, p := .p.l1
              end,
              q := .q.l1;
    edge tau when q = .q.l1 do q := .q.l2;
end

We see that the automata p and q are replaced by groups. They contain 'location pointer enumerations' LPE, with literals for their original locations. They also contain the linearized initialization and marker predicates of the locations. We further see that plant automata p and q are linearized to plant automaton M. Two location pointers, p and q, named after the original automata, are added. The discrete variables are moved. We have one location L, which is initial and marked. For event e, the guards and updates are linearized into a single self loop. Location pointer updates are incorporated as well. For event tau, the single original edge is simply included as a self loop. Within M, p refers to the location point variable and thus all references to objects in automaton p (now group p) use scope absolute references, e.g. .p.l1.

Non-determinism

If the original automata have non-determinism, this choice is eliminated as part of this transformation. Non-determinism can be present due to multiple outgoing edges for a single location, for the same event (excluding the tau event), with overlapping guards. Another cause of non-determinism is multiple senders or receivers that are enabled at the same time, for the same channel. In the resulting specification, the first possible transition is always taken, similar to how the simulator chooses, assuming the simulator is configured to always automatically choose the first transition. Linearization eliminates some of the non-determinism in this case, essentially choosing a specific trace through the state space. To ensure the same choices are made, events and automata are sorted in the same order for linearization and simulation.

For instance, the following specification:

automaton p:
  event e;
  disc int x = 0;

  location:
    initial;
    edge e when x < 5 do x := x + 1;
    edge e when x > 3 do x := x - 1;
end

is transformed to the following specification:

group p:
  event e;

  initial true and true;
  marked true and false;
end

automaton M:
  alphabet p.e;

  disc int p_x = 0;

  location L:
    initial;
    marked;

    edge p.e when true and (p_x < 5 or p_x > 3)
             do if true and p_x < 5: p_x := p_x + 1
                elif true and p_x > 3: p_x := p_x - 1
                end;
end

Here, we see that the edge for event p.e with guard x < 5 and update x := x + 1 is chosen to take precedence over the edge with guard x > 3 with update x := x - 1. This choice is based on the original specification, where the edge with guard x < 5 is listed before the edge with guard x > 3.

Related to this, are dummy updates, which are added to ensure that the correct updates are taken. For instance, the following specification:

automaton p:
  event e;
  disc int x = 0;
  location:
    initial;
    edge e when x >= 3;
    edge e when x < 3 do x := x + 1;
end

is transformed to the following specification:

group p:
  event e;

  initial true and true;
  marked true and false;
end

automaton M:
  alphabet p.e;

  disc int p_x = 0;

  location L:
    initial;
    marked;

    edge p.e when true and (p_x >= 3 or p_x < 3)
             do if true and p_x >= 3: p_x := p_x
                elif true and p_x < 3: p_x := p_x + 1
                end;
end

Here, the edge with guard x >= 3 takes precedence over the edge with guard x < 3. To ensure that no updates are performed when the edge with guard x >= 3 is chosen, a dummy update is added (reassigning the value of M.p_x to itself). If this update were to be omitted, the update of the other edge would instead be executed, which is undesirable.

Order

If code generation is performed on a linearized version of the specification, it may be a good idea to ensure the same order is used and the same choices are made, both in the generated code and in simulation. Assuming simulation was performed by always automatically choosing the first transition, this should correspond to the output of linearization. The linearized edges are in the same order as the transitions are calculated by the simulator. This is ensured by sorting events and automata in the same order for linearization and simulation. Also, as the Non-determinism section above explains, if non-determinism is eliminated, it is done in a way that preserves that order.

Code should thus be generated in the order of the linearized edges resulting from linearization. Each time the code for an edge is executed, the code should start from the top, to ensure always the first enabled transition is chosen.

Urgency

If the original automata contain urgent locations and/or urgent edges, a discrete boolean variable u is added to the linearized automaton. Initially, it’s value is true, and it must always remain so (plant invariant u;). We add self loops (event tau), with as guard the urgent locations and guards of urgent edges, such that the edge can be taken if the system is in an urgent location, or an urgent edge is enabled (guard wise). However, these edges update u to false, which violates the target location invariant, meaning we can never take these edges in a transition. Since the edge is also urgent, it means that if the edge is enabled guard wise, time may not progress, thus ensuring the urgency behavior of the original urgent locations and edges.

For instance, the following specification:

automaton p:
  event e;

  location l1:
    initial;
    urgent;
    edge e when true goto l2;

  location l2:
    edge e when 1 = 1 now goto l1;
end

is transformed to the following specification:

group p:
  event e;
  enum LPE = l1, l2;

  initial M.p = l1 and true or M.p = l2 and false;
  marked M.p = l1 and false or M.p = l2 and false;
end

automaton M:
  alphabet .p.e;

  disc .p.LPE p = .p.l1;
  disc bool u = true;

  plant invariant u;

  location L:
    initial;
    marked;

    edge .p.e when p = .p.l1 and true or p = .p.l2 and 1 = 1
              do if p = .p.l1 and true: p := .p.l2
                 elif p = .p.l2 and 1 = 1: p := .p.l1
                 end;

    edge when p = .p.l1 or p = .p.l2 and 1 = 1 now do u := false;
end

So, if M.p (the location pointer variable for original automaton p) is equal to p.l1 (the enumeration literal for original location l1), then the guard of the new urgent edge is enabled, and time may not progress. Similarly, if M.p is equal to p.l2 and the guard 1 = 1 of the original urgent edge is enabled, the guard of the new urgent edge is enabled, and time may not progress. This correctly reflects the urgency conditions of the original specification.

To ensure that no additional event transitions are possible, the new urgent edge can never be taken, as it would update u to false, which violates plant invariant u.

Received values and tuple field projections

The following specification:

event tuple(int a, b) e;

automaton s:
  location:
    initial;
    edge e!(1, 2);
end

automaton r:
  disc int x;
  location:
    initial;
    edge e? do x := ?[a];
end

is transformed to the following specification:

event e;

group s:
  initial true and true;
  marked true and false;
end

group r:
  initial true and true;
  marked true and false;
end

automaton M:
  alphabet e;

  disc int r_x;

  location L:
    initial;
    marked;

    edge e when true and true and (true and true) do r_x := (1, 2)[0];
end

Observe how event e no longer has a data type, and the communication (send and receive) have been eliminated. In the assignment x := ?[a], received value ? has been replaced by send value (1, 2). Since tuple values don’t have field names, the right hand side (1, 2)[a] has been replaced by (1, 2)[0], using the Eliminate tuple field projections CIF to CIF transformation.

Elimination of communication

Since channel communication is completely eliminated, and channels become regular events after this transformation, it is no longer possible to merge additional senders/receivers with the linearized specification. If you wish to merge another specification with additional communication partners, first perform the merging, and then the linearization.

Renaming

Since declarations are moved/merged, and new names are introduced, renaming may be necessary to ensure unique names within a single scope. If renaming is performed, a warning is printed to the console.

Size considerations

Variables are moved, so they don’t increase the size of the specification.

The addition of location pointer variables increases the size of the specification, but this is linear in the number of automata.

Assignment are added for the updates to the location pointers. The increase is linear in the number of edges. The additional dummy updates that are added are linear in the number of edges as well.

Since tau edges are essentially just moved, they don’t increase the size of the specification. That is, their size is linear in the number of original tau edges.

A single self loop is added for each non-tau event. This does increase the size of the specification. The guards are simply combined using boolean operators, and the increase is therefore linear in the number of guards. Similarly, updates are combined using 'if' updates, and the increase is also linear.

For original edges with multiple events however, the guards and updates are duplicated for each event. The duplication is linear in the number of events on those edges.

The initialization and marker predicates of locations, as well as the invariants of locations are moved. They remain linear in size related to the number of original predicates. The predicates are related to values of the location pointer variable. This size increase is linear in the number of original locations. Predicates are combined using boolean operators, leading to a size increase that is linear in the number of original predicates.

If a single received value is used multiple times in the updates of a single edge, the send value is duplicated for each of those uses. As such, the size increase is linear in the number of uses of the received value.

If multiple senders and multiple receivers (individual send/receive edges, not whole automata) are present for a certain event, then the received value is expanded to all the potential send values, with the conditions under which they are used as send value (using an 'if' expression). As such, the received value are expanded into expressions that are linear in the number of senders. If we have only a single sender or a single receiver, this is linear. If we have multiple of both, this becomes quadratic (number of senders times number of receivers).

For urgency, an additional variable and invariant are added. This is a constant increase in size. A self loop is added as well. This self loop duplicates the guards of urgent edges. It also includes predicates for the urgent locations. The size of this edge is linear in the number of urgent locations, and the guards of the urgent edges.

From the above, it should be clear that while the specification may increase in size, it is mostly linear. Practically, the size of the linearized specification is usually linear compared to the size of the input specification.

Optimality

As should be clear from the examples above, this transformation does not try to generate optimized expressions. In fact, often almost all generated expressions can easily be simplified. To further simplify the result, apply additional CIF to CIF transformations, such as Simplify values.

Currently, no effort is made by this transformation to reduce for instance the number of dummy assignments, or the number of replacements of tuple field projections by tuple index projections.

Annotations

This transformation does not process or add any annotations. The annotations of all locations of automata are lost, and the single new location does not have any annotations.