The Černý Conjecture and 1-Contracting Automata Article Swipe

PDF

Related Concepts

Synchronizing Automaton Conjecture Mathematics ω-automaton Set (abstract data type) Discrete mathematics State (computer science) Deterministic automaton Word (group theory) Combinatorics Two-way deterministic finite automaton Finite-state machine Timed automaton Quantum finite automata Automata theory Computer science Algorithm Theoretical computer science Topology (electrical circuits) Programming language Geometry

Henk Don ·

YOU? · · 2016 · Open Access · · DOI: https://doi.org/10.37236/5616 · OA: W2963544879

A deterministic finite automaton is synchronizing if there exists a word that sends all states of the automaton to the same state. Černý conjectured in 1964 that a synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. We introduce the notion of aperiodically 1-contracting automata and prove that in these automata all subsets of the state set are reachable, so that in particular they are synchronizing. Furthermore, we give a sufficient condition under which the Černý conjecture holds for aperiodically 1-contracting automata. As a special case, we prove some results for circular automata.