New characterizations of primitive permutation groups with applications to synchronizing automata

DOI10.1016/J.IC.2023.105086MaRDI QIDQ6186315zbMATH OpenFDO

Authors Stefan Hoffmann

Publication date 2 February 2024

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2023.105086

zbMATH Keywords

completely reachable automatafinite automatapairs of distinguishable subsetsprimitive permutation groupsset of synchronizing wordsstate complexitysynchronization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• Sync-maximal permutation groups equal primitive permutation groups
• Primitive groups, graph endomorphisms and synchronization
• Synchronizing groups and automata
• Between primitive and 2-transitive: synchronization and its friends

Cites work

• 4-homogeneous groups
• k-homogeneous groups
• A brief history of the classification of the finite simple groups
• A new proof of the Protasov-Voynov theorem on semigroups of nonnegative matrices
• A note on homogeneous experiments with finite automata
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• A Note on Two Set-Transitive Permutation Groups
• A remark about homogeneous experiments
• Automorphism groups of designs
• Between primitive and 2-transitive: synchronization and its friends
• Cerny's conjecture for automata with simple idempotents
• Completely distinguishable automata and the set of synchronizing words
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
• Constrained synchronization and commutativity
• Equivalence of topological Markov shifts
• Estimation of the length of reset words for automata with simple idempotents
• Generalized primitivity of labeled digraphs
• scientific article; zbMATH DE number 3811825 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• Intersection matrices for finite permutation groups
• Linear Automaton Transformations
• On primitivity of sets of matrices
• Primitive groups synchronize non-uniform maps of extreme ranks
• Primitive permutation groups and strongly factorizable transformation semigroups
• Primitive sets of nonnegative matrices and synchronizing automata
• Primitivity, uniform minimality, and state complexity of Boolean operations
• Reset complexity of ideal languages over a binary alphabet
• Set-Transitive Permutation Groups
• Sets of nonnegative matrices without positive products
• State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
• Sync-maximal permutation groups equal primitive permutation groups
• Synchronizing groups and automata
• The classification of partition homogeneous groups with applications to semigroup theory
• The road coloring problem
• The Synchronizing Probability Function for Primitive Sets of Matrices
• Theory of games and economic behavior.
• Transitivity of finite permutation groups on unordered sets
• Černý's conjecture and the road colouring problem

Cited in

(4)

• Adding a transformation to imprimitive transitive groups
• Subset mapping problems in solvable automata
• Completely reachable almost group automata
• Completely distinguishable automata and the set of synchronizing words

This page was built for publication: New characterizations of primitive permutation groups with applications to synchronizing automata

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