THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE

DOI10.1142/S0129054111008970zbMath1252.68185WikidataQ123218960 ScholiaQ123218960MaRDI QIDQ2909105

Benjamin Steinberg

Publication date: 29 August 2012

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

zbMATH Keywords

automatasynchronizationaveraging trickČerný conjecture

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items

Unnamed Item ⋮ Synchronizing Automata on Quasi-Eulerian Digraph ⋮ Synchronizing Automata with Extremal Properties ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Synchronizing sequences for road colored digraphs ⋮ Preimage problems for deterministic finite automata ⋮ On the Interplay Between Černý and Babai’s Conjectures ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ SYNCHRONIZING QUASI-EULERIAN AND QUASI-ONE-CLUSTER AUTOMATA ⋮ Algebraic synchronization criterion and computing reset words ⋮ Simplicity of augmentation submodules for transformation monoids ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ Experiments with Synchronizing Automata

Cites Work

• Synchronizing automata with a letter of deficiency 2
• Reset words for commutative and solvable automata
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic automata
• Composition sequences for functions over a finite domain.
• Černý's conjecture and group representation theory
• Synchronizing groups and automata
• SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
• Representation theory of finite semigroups, semigroup radicals and formal language theory