symbolic_dynamics.graphs.cernys_automata

symbolic_dynamics.graphs.cernys_automata(n)[source]

Returns the nth Cerny automata.

The nth Cerny automata is a fully deterministic graph C_n with states over {0, 1, …, n-1} with alphabet {a, b} with the following transition action:

  • sd.dot(C_n, i, "b") == i for i in range(n)

  • sd.dot(C_n, 0, "a") == 1

  • sd.dot(C_n, i, "a") == i for i in range(1, n)

The shortest synchronizing word for C_n is the word ("a"+"b"*(n-1))*(n-2)+"a", which has length of (n-1)**2.

Parameters
nint

Examples

>>> n = 5
>>> C_n = cernys_automata(n)
>>> w = ("a"+"b"*(n-1))*(n-2)+"a"
>>> len(sd.idot(C_n, C_n, w))
1