`automaton`

`.push_weights`

¶Push the weights towards in the initial states.

This algorithm uses a generalized shortest distance defined as:
\begin{align*}
d[q] = \bigoplus_{\pi \in P(q, F)} E(\pi)
\end{align*}

Where $P(q, F)$ is the set of paths from q to a final state, and $E(\pi)$ is the weight of the path $\pi$, i.e. the product of the weights of its transitions.

`push_weights`

is defined for any acyclic automaton, since $P(q, F)$ is finite for any state $q$.

For cyclic automata, $P(q, F)$ might be infinite, in which case `push_weights`

is guaranteed to terminate and to be correct only if the sum converges in a finite number of steps. Examples of automata verifying this property include

- automata with weights in $\mathbb{B}$
- automata with positive cycles and weights in $\mathbb{Z}_\text{min}$

Preconditions:

- The weightset is zero-sum-free and weakly divisible
- The shortest distance to the final state is defined for every state of the automaton

Postconditions:

- The Result is equivalent to the input automaton

In [1]:

```
import vcsn
```

The following example is taken from mohri.2009.hwa, Figure 12.

In [2]:

```
%%automaton --strip a
context = "lal_char, zmin"
$ -> 0
0 -> 1 <0>a, <1>b, <5>c
0 -> 2 <0>d, <1>e
1 -> 3 <0>e, <1>f
2 -> 3 <4>e, <5>f
3 -> $
```

In [3]:

```
a.push_weights()
```

Out[3]:

Note that weight pushing improves the "minimizability" of weighted automata:

In [4]:

```
a.minimize()
```

Out[4]:

In [5]:

```
a.push_weights().minimize()
```

Out[5]:

Again, the following example is taken from mohri.2009.hwa, Figure 12 (subfigure 12.d lacks two transitions), but computed in $\mathbb{Q}$ rather than $\mathbb{R}$ to render more readable results.

In [6]:

```
%%automaton --strip a
context = "lal_char, q"
$ -> 0
0 -> 1 <0>a, <1>b, <5>c
0 -> 2 <0>d, <1>e
1 -> 3 <0>e, <1>f
2 -> 3 <4>e, <5>f
3 -> $
```

In [7]:

```
a.push_weights()
```

Out[7]: