Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1152.68461
Trahtman, Avraham N.
The Černý conjecture for aperiodic automata. (English)
[J] Discrete Math. Theor. Comput. Sci. 9, No. 2, 3-10, electronic only (2007). ISSN 1365-8050/e

Summary: A word w is called a synchronizing (recurrent, reset, directable) word of a deterministic finite automaton (DFA) if w brings all states of the automaton to some specific state; a DFA that has a synchronizing word is said to be synchronizable. Cerny conjectured in 1964 that every n-state synchronizable DFA possesses a synchronizing word of length at most $(n-1)^2$. We consider automata with aperiodic transition monoid (such automata are called aperiodic). We show that every synchronizable $n$-state aperiodic DFA has a synchronizing word of length at most $n(n-1)/2$. Thus, for aperiodic automata as well as for automata accepting only star-free languages, the Cerny conjecture holds true.

MSC 2000:: *68Q45 Formal languages

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]