automaton.synchronizing_word(algo)

See also:

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
%3 0 0 0->0 a 1 1 0->1 b 1->0 a 1->1 b 2 2 2->0 b 2->1 a

Synchronization checks

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

In [3]:
a.is_synchronizing()
Out[3]:
True

We can guess from the figure that $aa$ is a synchronizing word of $\mathcal{A}$. We can verify that with is_synchronized_by:

In [4]:
a.is_synchronized_by('aa')
Out[4]:
True

Algorithms

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)

Greedy

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]:
$\mathit{baababaaab}$

Cycle

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]:
$\mathit{baaabaaab}$

SynchroP & SynchroPL

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]:
$\mathit{baaabaaab}$

SynchroPL is similar to SynchroP but adds the distance of the synchronized pair as a "cost" in the heuristic. Its time complexity is also $O(n^5)$.

In [9]:
a.synchronizing_word('synchropl')
Out[9]:
$\mathit{baaabaaab}$

FastSynchro

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]:
$\mathit{baaabaaab}$

Synchronizing words for transducers

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
%3 0 0 1 1 0->1 [^a|d] 2 2 0->2 a|d 1->0 a|d, b|c 1->1 a|c 1->2 b|d 2->1 [^b|c] 2->2 b|c
In [12]:
t.synchronizing_word()
Out[12]:
$\mathit{a},\mathit{c}$
In [13]:
t.is_synchronized_by(t.synchronizing_word('fastsynchro'))
Out[13]:
True
In [14]:
t.pair()
Out[14]:
%3 0 0 0->0 [^] 1 0, 1 1->0 a|c 1->1 b|c 2 0, 2 1->2 a|d 3 1, 2 1->3 b|d 2->0 a|c, b|d 2->3 a|d, b|c 3->0 a|c 3->1 a|d 3->2 b|c 3->3 b|d