New characterizations of primitive permutation groups with applications to synchronizing automata

DOI10.1016/j.ic.2023.105086MaRDI QIDQ6186315

Stefan Hoffmann

Publication date: 2 February 2024

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

zbMATH Keywords

primitive permutation groupssynchronizationfinite automatastate complexityset of synchronizing wordscompletely reachable automatapairs of distinguishable subsets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primitive groups synchronize non-uniform maps of extreme ranks
• Sets of nonnegative matrices without positive products
• The road coloring problem
• On primitivity of sets of matrices
• Equivalence of topological Markov shifts
• Generalized primitivity of labeled digraphs
• Černý's conjecture and the road colouring problem
• Sync-maximal permutation groups equal primitive permutation groups
• Cerny's conjecture for automata with simple idempotents
• Primitive permutation groups and strongly factorizable transformation semigroups
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
• Constrained synchronization and commutativity
• Algebraic synchronization criterion and computing reset words
• Primitivity, uniform minimality, and state complexity of Boolean operations
• A new proof of the Protasov-Voynov theorem on semigroups of nonnegative matrices
• Between primitive and 2-transitive: synchronization and its friends
• Synchronizing groups and automata
• Transitivity of finite permutation groups on unordered sets
• Intersection matrices for finite permutation groups
• 4-homogeneous groups
• Automorphism groups of designs
• \(k\)-homogeneous groups
• A brief history of the classification of the finite simple groups
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• Primitive Sets of Nonnegative Matrices and Synchronizing Automata
• Linear Automaton Transformations
• A Note on Two Set-Transitive Permutation Groups
• Reset Complexity of Ideal Languages Over a Binary Alphabet
• Set-Transitive Permutation Groups
• The Synchronizing Probability Function for Primitive Sets of Matrices
• Estimation of the length of reset words for automata with simple idempotents
• The classification of partition homogeneous groups with applications to semigroup theory
• Completely distinguishable automata and the set of synchronizing words
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees

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