Synchronizing groups and automata

DOI10.1016/j.tcs.2006.02.003zbMath1097.68054OpenAlexW2001279658MaRDI QIDQ2503289

Benjamin Steinberg, Fredrick Arnold

Publication date: 14 September 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.02.003

zbMATH Keywords

synchronizationfinite automataCerny problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Characterization theorems for permutation groups (20B10)

Related Items

Imprimitive permutations in primitive groups, THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE, Orbits of primitive $k$-homogenous groups on $(n-k)$-partitions with applications to semigroups, CORES OF SYMMETRIC GRAPHS, A transversal property for permutation groups motivated by partial transformations, Groups synchronizing a transformation of non-uniform kernel, Primitive groups synchronize non-uniform maps of extreme ranks, Synchronizing automata with coinciding cycles, Effective dimension of finite semigroups., Primitive groups, graph endomorphisms and synchronization, New characterizations of primitive permutation groups with applications to synchronizing automata, Primitive permutation groups and strongly factorizable transformation semigroups, Groups that together with any transformation generate regular semigroups or idempotent generated semigroups., The existential transversal property: A generalization of homogeneity and its impact on semigroups, Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words, Möbius functions and semigroup representation theory. II: Character formulas and multiplicities., A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number, Černý's conjecture and group representation theory, A note on the rank of semigroups., The Černý conjecture for one-cluster automata with prime length cycle, Two generalizations of homogeneity in groups with applications to regular semigroups, Semisimple Synchronizing Automata and the Wedderburn-Artin Theory, The classification of partition homogeneous groups with applications to semigroup theory, Representation theory of finite semigroups, semigroup radicals and formal language theory, Simplicity of augmentation submodules for transformation monoids, Matrix Mortality and the Černý-Pin Conjecture, Primitive permutation groups and their section-regular partitions., Cliques and colorings in generalized Paley graphs and an approach to synchronization, Sync-maximal permutation groups equal primitive permutation groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Synchronizing finite automata on Eulerian digraphs.
• Permutation representations and rational irreducibility
• Studies in the Representation Theory of Finite Semigroups