Talk:Synchronizing word
Add topic | This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
| ||||||||||||||||||
merge
[edit]I suggest merging the entire section Self-synchronizing code#Synchronizing word into this Synchronizing word article, possibly leaving behind a short summary (Wikipedia: Summary style). --DavidCary (talk) 19:09, 23 November 2015 (UTC)
- The definitions look different to me. The definition of a synchronizing word given here is specific to a particular automaton — different automata that recognize the same language as each other have different synchronizing words — while the definition there is independent of any automaton. And what about automata that do not recognize codes? Per WP:NOTDICT, we should have articles about concepts, not articles about the phrases that name those concepts, so having two different concepts with the same name is a bad reason for a proposed merge. —David Eppstein (talk) 21:36, 23 November 2015 (UTC)
"Černý conjecture" and his 1964 paper
[edit]This paper[1]
At first author prooved that automata Uk (classic "Černý automata" with k states) is synchronizable by word of length (k-1)2 and not synchronizable by any shorter word ("Lema 1", page 213-214).
Then author noted that any synchronizable automata is synchronizable by word of length not more than 2k - k - 1 ("Lema 2", page 214-215).
Eventually author combined "Lema 1" and "Lema 2": maximum of shortest synchronizing words has length between (k-1)2 and 2k - k - 1 ("Veta 3", page 215).
So there is no conjecture that "(k − 1)2 is the upper bound for the length of the shortest synchronizing word".
Maybe this conjecture noted in another paper. — Preceding unsigned comment added by 82.193.140.165 (talk) 18:39, 16 March 2018 (UTC)
References
- ↑ Černý, J. (1964), "Poznámka k homogénnym experimentom s konečnými automatami" (PDF), Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied, 14: 208–216 (in Slovak).
- I can confirm the above, noting also that Černý ends the paper with a laconic statement “For larger k, there is a considerable gap between the lower and upper bound, hence it would be desirable to improve them. One can expect that especially the upper bound is not tight.” That’s all there is in the paper in the way of conjecture.—Emil J. 14:42, 5 April 2019 (UTC)