In [1]:

```
import vcsn
c = vcsn.context('lal_char(ab), b')
```

Let's take a simple 3-state automaton $\mathcal{A}$:

In [2]:

```
%%automaton -s a
context = "lal_char(ab), b"
0 -> 0 a
0 -> 1 b
1 -> 0 a
1 -> 1 b
2 -> 0 b
2 -> 1 a
```

We can check that $\mathcal{A}$ is synchronizing:

In [3]:

```
a.is_synchronizing()
```

Out[3]:

`is_synchronized_by`

:

In [4]:

```
a.is_synchronized_by('aa')
```

Out[4]:

To find a short synchronizing word, we need to use the `synchronizing_word()`

method, which takes an algorithm in paramater.
The default algorithm is `greedy`

, when no algorithm is specified.

In [5]:

```
a = c.cerny(4)
```

Eppstein's greedy is a $O(n^3)$ greedy algorithm which always synchronizes the closest pair first.
It can be called using `synchronizing_word('greedy')`

or `synchronizing_word('eppstein')`

In [6]:

```
a.synchronizing_word('greedy')
```

Out[6]:

Cycle is a $O(n^3)$ algorithm similar to Greedy, which ensures that the pair synchronized contains the latest singleton in which the synchronization previously took place. This is less efficient in the general case but gives optimal results ($(n - 1)^2$) for Černý automata.

In [7]:

```
a.synchronizing_word('cycle')
```

Out[7]:

SynchroP is a "one-step ahead" heuristic with a $O(n^5)$ time complexity that checks the distance of the new active states from $q_0$ after synchronizing a specific pair, and tries to minimize the sum of these distances.

In [8]:

```
a.synchronizing_word('synchrop')
```

Out[8]:

In [9]:

```
a.synchronizing_word('synchropl')
```

Out[9]:

FastSynchro finds labels that reduces the new distances of the active states when appended to the synchronizing word. To guarantee that the algorithm terminates, it is only used if the label reduces the overall distance. If not, a bounded SynchroPL heuristic is used. The complexity of this algorithm is $O(n^3)$.

In [10]:

```
a.synchronizing_word('fastsynchro')
```

Out[10]:

All the algorithms can also be used with k-tapes transducers:

In [11]:

```
%%automaton -s t
context = "lat<lal_char(ab), lal_char(cd)>, b"
0 -> 1 a|c, b|c, b|d
0 -> 2 a|d
1 -> 0 a|d, b|c
1 -> 1 a|c
1 -> 2 b|d
2 -> 1 a|c, a|d, b|d
2 -> 2 b|c
```

In [12]:

```
t.synchronizing_word()
```

Out[12]:

In [13]:

```
t.is_synchronized_by(t.synchronizing_word('fastsynchro'))
```

Out[13]:

In [14]:

```
t.pair()
```

Out[14]: