|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Cerny-Starke conjecture from the sixties of XX century | | A.N. Trahtman
; | | Date: |
13 Mar 2020 | | Abstract: | A word $w$ of letters on edges of underlying graph $Gamma$ of deterministic
finite automaton (DFA) is called synchronizing if $w$ sends all states of the
automaton to a unique state.
J. v{C}erny discovered in 1964 a sequence of $n$-state complete DFA
possessing a minimal synchronizing word of length $(n-1)^2$. The hypothesis,
well known today as v{C}erny conjecture, claims that $(n-1)^2$ is a precise
upper bound on the length of such a word over alphabet $Sigma$ of letters on
edges of $Gamma$ for every complete $n$-state DFA. The hypothesis was
formulated distinctly in 1966 by Starke.
A special classes of matrices induced by words in the alphabet of labels on
edges of the underlying graph of DFA are used to prove the conjecture. | | Source: | arXiv, 2003.6177 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER