A395449 Smallest sum of synchronizing word lengths of an n-state binary deterministic finite automaton that has a synchronizing word for every state.

7, 10, 14, 18, 22, 26, 31, 36, 41

Offset

3,1

Comments

A synchronizing word of a deterministic finite automaton (DFA) is a word in its input alphabet that sends any state to one and the same state s. Here we are interested in DFAs that have a synchronizing word for every state s. Note that self-loops are not allowed.

These values are the best known lower bounds obtained with a hill-climbing program and are not yet proven to be optimal.

Links

Table of n, a(n) for n=3..11.

Puzzling StackExchange, The emperor's magic trick: the omnipotent compass.

Wikipedia, Synchronizing word.

Example

Consider the following 3-state binary DFA. Edges labeled A: 0 -> 2, 1 -> 2, 2 -> 0. Edges labeled B: 0 -> 1, 1 -> 0, 2 -> 1. States 0, 1 and 2 are reached from any state with the words BAA, AB and BA, respectively. Since this is the DFA with the smallest sum of synchronizing words, we have a(3) = 7.

Crossrefs

Sequence in context: A005526 A192292 A030123 * A191833 A020752 A134302

Adjacent sequences: A395446 A395447 A395448 * A395450 A395451 A395452

Keyword

nonn,more

Author

Dmitry Kamenetsky, Apr 23 2026

Status

approved