Between primitive and 2-transitive: synchronization and its friends (Q2412925)

This contribution summarizes the progress on the Černy conjecture, which states that each synchronizing automaton has a reset word of length at most \((n-1)^2\), where \(n\) is the number of states of the automaton. It aims to provide a unified reference for all the algebraic approaches that have been pursued in the past. A synchronizing automaton is a deterministic finite-state automaton such that there exists a word, called reset word, and a state \(q\) such that the reset word takes each state into the state \(q\). The Černy conjecture asks for the length of a shortest reset word of a synchronizing automaton and proposes that its length is at most \((n-1)^2\), where \(n\) is the number of states of the deterministic automaton. In other words, if an automaton has a reset word, then it also has a reset word of quadratic length under the Černy conjecture. To each automaton we can associate its transformation monoid in which the generators essentially describe how the alphabet symbols act on the states. In this setting, the automaton is synchronizing if these generators can generate a constant map. The only example of a family of slowly synchronizing automata, due to Černy himself, which uses two alphabet symbols, of which one acts as a permutation on the states and the other is a non-permutation, provides the motivation for the main definition. A group (e.g., the one generated by the permutations) is synchronizing if it synchronizes every non-permutation \(f\) on the same set in the sense that the generators of the group and \(f\) can generate an element of rank 1 (e.g. a constant map). The contribution then investigates these synchronizing groups and places them into the hierarchy of groups. Although the Černy conjecture started these detailed investigations, synchronizing groups are interesting in their own right as a class of non-trivial groups with interesting properties. The survey presents most of them in a unified way suitable for a standard reference. The contribution is very well written and remains accessible despite the very algebraic approach covered. The authors make every effort to motivate definitions, illustrate them on well-chosen examples and provide suitable intuition. The material additionally is extremely self-contained and can be understood without reference to algebra textbooks. Only very few basic concepts like permutation groups are not detailed in the contribution. Overall, this survey provides an excellent starting point for anyone entering the area of synchronizing groups or the hunt for the Černy conjecture and requires only a graduate level of expertise in mathematics.