Name
Abstract | ||
|---|---|---|
A synchronizing word w for a given synchronizing DFA is called minimal if no proper prefix or suffix of w is synchronizing. We characterize the class of synchronizing automata having finite language of minimal synchronizing words (such automata are called finitely generated ). Using this characterization we prove that any such automaton possesses a synchronizing word of length at most 3n *** 5. We also prove that checking whether a given DFA $\mathcal{A}$ is finitely generated is co-NP-hard, and provide an algorithm for this problem which is exponential in the number of states $\mathcal{A}.$ |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-00982-2_57 | LATA |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Exponential function,Suffix,Computer science,Synchronizing,Automaton,Prefix,Synchronizing word,Regular language,True quantified Boolean formula | Conference | 5457 |
ISSN | Citations | PageRank |
0302-9743 | 5 | 1.24 |
References | Authors | |
4 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elena V. Pribavkina | 1 | 52 | 9.22 |
| Emanuele Rodaro | 2 | 55 | 15.63 |