Between primitive and 2-transitive: synchronization and its friends

DOI10.4171/EMSS/4-2-1MaRDI QIDQ2412925zbMATH OpenFDO

Authors João Araújo, Peter J. Cameron, Benjamin Steinberg

Publication date 6 April 2018

Published in EMS Surveys in Mathematical Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.03184

zbMATH Keywords

2-transitivefinite-state automatagraphorbitalovoidprimitive groupreset wordseparating groupspreadspreading groupsurveysynchronizing automatonsynchronizing grouptransformation semigroupČerný conjecture

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) General theory for finite permutation groups (20B05) Semigroups of transformations, relations, partitions, etc. (20M20) Semigroups in automata theory, linguistics, etc. (20M35) Polar geometry, symplectic spaces, orthogonal spaces (51A50) Algebraic theory of languages and automata (68Q70)

Abstract: An automaton is said to be synchronizing if there is a word in the transitions which sends all states of the automaton to a single state. Research on this topic has been driven by the v{C}ern'y conjecture, one of the oldest and most famous problems in automata theory, according to which a synchronizing $n$-state automaton has a reset word of length at most $(n-1{)}^2$. The transitions of an automaton generate a transformation monoid on the set of states, and so an automaton can be regarded as a transformation monoid with a prescribed set of generators. In this setting, an automaton is synchronizing if the transitions generate a constant map. A permutation group $G$ on a set $Omega$ is said to synchronize a map $f$ if the monoid $langleG,fangle$ generated by $G$ and $f$ is synchronizing in the above sense; we say $G$ is synchronizing if it synchronizes every non-permutation. The classes of synchronizing groups and friends form an hierarchy of natural and elegant classes of groups lying strictly between the classes of primitive and $2$-homogeneous groups. These classes have been floating around for some years and it is now time to provide a unified reference on them. The study of all these classes has been prompted by the v{C}ern'y conjecture, but it is of independent interest since it involves a rich mix of group theory, combinatorics, graph endomorphisms, semigroup theory, finite geometry, and representation theory, and has interesting computational aspects as well. So as to make the paper self-contained, we have provided background material on these topics. Our purpose here is to present results that show the connections between the various areas of mathematics mentioned above, we include a new result on the v{C}ern'y conjecture, some challenges to finite geometers, some thoughts about infinite analogues, and a long list of open problems.

Review text

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.

Recommendations

• The Černý conjecture for automata respecting intervals of a directed graph
• Composition sequences and synchronizing automata
• The Černý conjecture for one-cluster automata with prime length cycle
• Semisimple synchronizing automata and the Wedderburn-Artin theory
• The Černý conjecture for aperiodic automata

Cited in

(50)

• Primitive permutation groups and their section-regular partitions.
• On two problems of almost synchronizing groups
• Congruences on direct products of transformation and matrix monoids
• Asymptotic enumeration of Cayley digraphs
• Simplicity of augmentation submodules for transformation monoids
• Sync-maximal permutation groups equal primitive permutation groups
• On the asymptotic enumeration of Cayley graphs
• Primitive permutation groups and strongly factorizable transformation semigroups
• Preimage problems for deterministic finite automata
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• Černý's conjecture and group representation theory
• The Hall-Paige conjecture, and synchronization for affine and diagonal groups
• Primitivity, uniform minimality, and state complexity of Boolean operations
• Imprimitive permutations in primitive groups
• On ideals of quasi-commutative semigroups
• Synchronizing groups and automata
• A transversal property for permutation groups motivated by partial transformations
• Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
• Composition sequences and synchronizing automata
• Primitive groups, graph endomorphisms and synchronization
• Permutation groups and transformation semigroups: results and problems.
• Primitive sets of nonnegative matrices and synchronizing automata
• Automorphisms of shift spaces and the Higman-Thompson groups: the one-sided case
• Dixon's theorem and random synchronization
• Groups synchronizing a transformation of non-uniform kernel
• Orbits of primitive k-homogeneous groups on (n-k)-partitions with applications to semigroups
• The geometry of diagonal groups
• The existential transversal property: a generalization of homogeneity and its impact on semigroups
• On the interplay between Černý and Babai's conjectures
• The classification of partition homogeneous groups with applications to semigroup theory
• Pre-primitive permutation groups
• Completely distinguishable automata and the set of synchronizing words
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
• Synchronising primitive groups of diagonal type exist
• Normalish Amenable Subgroups of the R. Thompson Groups
• Separating rank 3 graphs
• The road problem and homomorphisms of directed graphs
• Binary and circular automata having maximal state complexity for the set of synchronizing words
• New characterizations of primitive permutation groups with applications to synchronizing automata
• Reset thresholds of transformation monoids
• The synchronisation hierarchy via coherent configurations
• Conjugacy for certain automorphisms of the one-sided shift via transducers
• Short synchronizing words for random automata
• Tactical decompositions in finite polar spaces and non-spreading classical group actions
• Completely distinguishable automata and the set of synchronizing words
• A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group
• The non-synchronizing primitive groups of degree up to 624
• Conjugacy in abstract semigroups, transformation and diagram monoids and conjugacy growth
• Separating subsets from their images
• The complexity of reachability problems in strongly connected finite automata

This page was built for publication: Between primitive and 2-transitive: synchronization and its friends

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2412925)