pith. sign in

arxiv: 1507.06070 · v2 · pith:BO4WZWZHnew · submitted 2015-07-22 · 🧮 math.CO · cs.FL

The Cerny conjecture and 1-contracting automata

classification 🧮 math.CO cs.FL
keywords automatasynchronizingautomatoncontractingaperiodicallyconjectureprovestate
0
0 comments X
read the original abstract

A deterministic finite automaton is synchronizing if there exists a word that sends all states of the automaton to the same state. \v{C}ern\'y 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 \v{C}ern\'y conjecture holds for aperiodically $1-$contracting automata. As a special case, we prove some results for circular automata.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.