Name
Abstract | ||
|---|---|---|
A word w is called synchronizing (recurrent, reset, directable) word of deterministic finite automata (DFA) if w brings all states of the automaton to a unique state. According to the famous conjecture of Černý from 1964, every n-state synchronizing automaton possesses a synchronizing word of length at most (n–1)2. The problem is still open. It will be proved that the Černý conjecture holds good for synchronizing DFA with transition
monoid having no involutions and for every n-state (n > 2) synchronizing DFA with transition monoid having only trivial subgroups the minimal length of synchronizing word is not
greater than (n–1)2/2. The last important class of DFA involved and studied by Schŭtzenberger is called aperiodic; its automata accept precisely star-free languages. Some properties of an arbitrary synchronizing DFA were established. See
http://www.cs.biu.ac.il/~trakht/syn.html. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s11390-008-9165-4 | J. Comput. Sci. Technol. |
Keywords | Field | DocType |
synchronization,erny conjecture,deterministic finite automata (dfa),aperiodic semigroup,deterministic finite automata | Discrete mathematics,Computer science,Deterministic finite automaton,Synchronizing,Algorithm,Monoid,DFA minimization,Synchronizing word,Aperiodic semigroup,Aperiodic graph,Conjecture,Distributed computing | Journal |
Volume | Issue | ISSN |
23 | 5 | 1860-4749 |
Citations | PageRank | References |
2 | 0.65 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Avraham Trakhtman | 1 | 13 | 2.15 |
| A. N. Trahtman | 2 | 92 | 11.68 |