On the Interplay Between Černý and Babai’s Conjectures

DOI10.1142/S0129054119400057zbMath1415.68129arXiv1704.04047OpenAlexW2918956746WikidataQ123284435 ScholiaQ123284435MaRDI QIDQ5384433

François Gonze, Balázs Gerencsér, Raphaël M. Jungers, Vladimir V. Gusev, Mikhail V. Volkov

Publication date: 24 June 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Černý's conjecturesynchronizing automataBabai's conjecturepermutation automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Unnamed Item ⋮ Černý's conjecture and the road colouring problem

Cites Work

• The Černý conjecture and 1-contracting automata
• Primitive digraphs with large exponents and slowly synchronizing automata
• Dixon's theorem and random synchronization
• The Černý conjecture for one-cluster automata with prime length cycle
• Computing modular coincidences for substitution tilings and point sets
• Classical finite transformation semigroups. An introduction.
• An extremal problem for two families of sets
• On the diameter of permutation groups
• Reset words for commutative and solvable automata
• Synchronizing finite automata on Eulerian digraphs.
• Composition sequences for functions over a finite domain.
• On the interplay between Babai and Černý's conjectures
• Between primitive and 2-transitive: synchronization and its friends
• On the diameter of permutation groups.
• Preset Distinguishing Sequences and Diameter of Transformation Semigroups
• On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata
• Completely Reachable Automata
• THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• Primitive Sets of Nonnegative Matrices and Synchronizing Automata
• Synchronizing Automata and the Černý Conjecture
• SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
• On two Combinatorial Problems Arising from Automata Theory
• The action of a few permutations onr-tuples is quickly transitive
• Growth in groups: ideas and perspectives
• IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
• The probability of generating the symmetric group
• Estimation of the length of reset words for automata with simple idempotents
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item