Groups synchronizing a transformation of non-uniform kernel

DOI10.1016/J.TCS.2013.06.016MaRDI QIDQ391192zbMATH OpenOpenAlexFDO

Authors João Araújo, Wolfram Bentz, Peter J. Cameron

Publication date 10 January 2014

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

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

zbMATH Keywords

permutation groupprimitive groupssemigroups of transformationsalmost synchronizing groupsfinite automorphism groupspseudo-coressynchronizing automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Primitive groups (20B15) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: This paper concerns the general problem of classifying the finite deterministic automata that admit a synchronizing (or reset) word. (For our purposes it is irrelevant if the automata has initial or final states.) Our departure point is the study of the transition semigroup associated to the automaton, taking advantage of the enormous and very deep progresses made during the last decades on the theory of permutation groups, their geometry and their combinatorial structure. Let $X$ be a finite set. We say that a primitive group $G$ on $X$ is {em synchronizing} if $G$ together with any non-invertible map on $X$ generates a constant map. It is known (by some recent results proved by P. M. Neumann) that for some primitive groups $G$ and for some singular transformations $t$ of uniform kernel (that is, all blocks have the same number of elements), the semigroup $<G,t>$ does not generate a constant map. Therefore the following concept is very natural: a primitive group $G$ on $X$ is said to be {em almost synchronizing} if $G$ together with any map of non-uniform kernel generates a constant map. In this paper we use two different methods to provide several infinite families of groups that are not synchronizing, but are almost synchronizing. The paper ends with a number of problems on synchronization likely to attract the attention of experts in computer science, combinatorics and geometry, groups and semigroups, linear algebra and matrix theory.

Recommendations

• Synchronizing almost-group automata
• Imprimitive groups synchronizing a transformation of non-uniform kernel
• Synchronizing random almost-group automata
• Primitive groups, graph endomorphisms and synchronization
• Between primitive and 2-transitive: synchronization and its friends

Cites work

• scientific article; zbMATH DE number 3605922 (Why is no real title available?)
• scientific article; zbMATH DE number 1962784 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 3402743 (Why is no real title available?)
• CORES OF SYMMETRIC GRAPHS
• Cores of geometric graphs
• Kneser's conjecture, chromatic number, and homotopy
• On parallelisms in finite projective spaces
• On the intersection of ovoids sharing a polarity
• On the probability of being synchronizable
• Partitioning the planes of \(AG_{2m}(2)\) into 2-designs
• Primitive permutation groups and their section-regular partitions.
• Reset Sequences for Monotonic Automata
• SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
• Self-stabilizing systems in spite of distributed control
• Some New Features and Algorithms for the Study of DFA
• Synchronizing groups and automata
• Synchronizing monotonic automata
• The maximum size of the intersection of two ovoids
• The Černý conjecture for aperiodic automata

Cited in

(15)

• Cliques and colorings in generalized Paley graphs and an approach to synchronization
• Primitive groups, graph endomorphisms and synchronization
• Synchronizing groups and automata
• The classification of partition homogeneous groups with applications to semigroup theory
• Primitive groups synchronize non-uniform maps of extreme ranks
• Synchronizing random almost-group automata
• Reset complexity and completely reachable automata with simple idempotents
• Orbits of primitive \(k\)-homogeneous groups on \((n-k)\)-partitions with applications to semigroups
• Synchronizing almost-group automata
• A transversal property for permutation groups motivated by partial transformations
• Imprimitive groups synchronizing a transformation of non-uniform kernel
• On two problems of almost synchronizing groups
• On the probability of being synchronizable
• The existential transversal property: a generalization of homogeneity and its impact on semigroups
• Primitive permutation groups and strongly factorizable transformation semigroups

This page was built for publication: Groups synchronizing a transformation of non-uniform kernel

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