Linearize (product)

> > >

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

This transformation maintains 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. To eliminate non-determinism, resulting in specifications with smaller state spaces, at the expense of not preserving the specification’s full behavior, use the linearize (merge) 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 Cartesian product of all edges is created, combining the edges in all possible combinations. This results in self loops for all non-tau events, where the combination of all self loops maintains all non-deterministic choices of the original specification. Worst case, the model size of the resulting specification compared to the model size of the original specification could blow up exponentially.

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 and q = .q.l2)
           do p_x := 2, p := .p.l2, q := .q.l1;
    edge e when p = .p.l2 and (p_x = 2 and q = .q.l2)
           do p_x := 1, p := .p.l1, 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, two self loop edges are added, as automaton p has two edges for e and automaton q has one edge for e and 2 * 1 is 2. For the self loop edges, the guards and updates are combined. 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 maintained 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, all possible combinations are included as self loops. For a specification with 4 sender automata with two send edges each (8 send edges in total) and 5 receiver automata with two receive edges each (10 receive edges in total) for event e, and also 6 automata with two edges each that synchronize over that event (12 synchronization edges in total), the number of possible combinations for communication with synchronization is 8 * 10 * 12, which is 960 possible combinations.

For instance, the following specification:

event e;

automaton p:
  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

automaton q:
  disc int y = 0;

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

is transformed to the following specification:

event e;

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

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

automaton M:
  alphabet e;

  disc int p_x = 0;
  disc int q_y = 0;

  location L:
    initial;
    marked;

    edge e when p_x < 5 and q_y < 5
           do p_x := p_x + 1, q_y := q_y + 1;
    edge e when p_x < 5 and q_y > 3
           do p_x := p_x + 1, q_y := q_y - 1;
    edge e when p_x < 5 and q_y = 4
           do p_x := p_x + 1, q_y := q_y - 1;
    edge e when p_x > 3 and q_y < 5
           do p_x := p_x - 1, q_y := q_y + 1;
    edge e when p_x > 3 and q_y > 3
           do p_x := p_x - 1, q_y := q_y - 1;
    edge e when p_x > 3 and q_y = 4
           do p_x := p_x - 1, q_y := q_y - 1;
end

Here, we see that for event e, automaton p has two edges and automaton q has three edges. The linearization result has six edges.

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.

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 do p := .p.l2;
    edge .p.e when p = .p.l2 and 1 = 1 do p := .p.l1;
    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 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.

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.

Multiple self loops may be added for non-tau event, and thus may result in an exponential blow up of the number of 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.

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 due to the exponential blow up of the edges, linearization results can be significantly larger than the original specifications.

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 replacements of tuple field projections by tuple index projections.