

![0_image_0.png](0_image_0.png)

- *nbrPaths*[1 ≤ i ≤ n,1 ≤ j ≤ m] records the number of paths from node j in layer i to a success node in the last layer; for example, see the numbers by each node in Figure 2;
- ℓ is the number of segments in the current segmentation;
- segments σ1,...,σℓ record the current segmentation;
- *Violation*[1 ≤ i ≤ n] records the current violation of decision variable Vi (see Definition 3);
The *nbrPaths* matrix can be computed in straightforward fashion by dynamic programming. The other three data structures are initialised (when the starting position is s = 1) and maintained (when decision variable Vsis changed, with s ≥ 1) by the *calcSegment*(s) procedure of Algorithm 1. Upon some initialisations (lines 2 and 3), it (re)visits only the decision variables Vs,...,Vn (line 4). If the value of the currently visited decision variable Vitriggers the extension of the currently last segment (lines 6 and 9)
or the creation of a new segment (lines 6 to 9), then its violation is 0 (line 10). Otherwise, its violation is 1 and a successor node is picked with a probability weighted according to the number of paths from the current node to a success node (lines 11 to 14). Toward this, we maintain the nodes of the picked path
(line 16).

The time complexity of Algorithm 1 is linear in the number n of decision variables, because only one path (from layer s to layer n + 1) is explored, with a constant-time effort at each node. Once the pre-processing is done, the time complexity of Algorithm 1 is thus *independent* of the number of arcs of the unrolled automaton! Hence the minimisation (or reduction) of the unrolled automaton would be merely for space savings (and for the convenience of human reading) as well as for accelerating the preprocessing computation of the *nbrPaths* matrix. In our experiments, these space and time savings are not warranted by the time required for minimisation (or reduction).

Note that this algorithm works *without* change or loss of performance on non-deterministic finite automata (NFAs). This is potentially interesting since NFAs are often smaller than their equivalent DFAs, but (as just seen) the number of arcs has no influence on the time complexity of Algorithm 1.