Groups synchronizing a transformation of non-uniform kernel

DOI10.1016/J.TCS.2013.06.016zbMATH Open1295.68162arXiv1205.0682OpenAlexW2117905774MaRDI QIDQ391192FDOQ391192

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)

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.

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

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

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)

Cites Work

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

Cited In (13)

• Primitive groups synchronize non-uniform maps of extreme ranks
• Reset complexity and completely reachable automata with simple idempotents
• A transversal property for permutation groups motivated by partial transformations
• On two problems of almost synchronizing groups
• Imprimitive groups synchronizing a transformation of non-uniform kernel
• Orbits of primitive $k$-homogenous groups on $(n-k)$-partitions with applications to semigroups
• Synchronizing groups and automata
• On the Probability of Being Synchronizable
• Primitive groups, graph endomorphisms and synchronization
• The existential transversal property: A generalization of homogeneity and its impact on semigroups
• The classification of partition homogeneous groups with applications to semigroup theory
• Cliques and colorings in generalized Paley graphs and an approach to synchronization
• 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)