DFAs and PFAs with Long Shortest Synchronizing Word Length

Autor: de Bondt, Michiel, Don, Henk, Zantema, Hans

It was conjectured by \v{C}ern\'y in 1964, that a synchronizing DFA on $n$ states always has a shortest synchronizing word of length at most $(n-1)^2$, and he gave a sequence of DFAs for which this bound is reached. Until now a full analysis of all D

Externí odkaz: http://arxiv.org/abs/1703.07618

Modifying the upper bound on the length of minimal synchronizing word

Autor: Trahtman, A. N.

A word $w$ is called synchronizing (recurrent, reset, magic, directable) word of deterministic finite automaton (DFA) if $w$ sends all states of the automaton to a unique state. In 1964 Jan \v{C}erny found a sequence of n-state complete DFA possessin

Externí odkaz: http://arxiv.org/abs/1104.2409

Finding DFAs with Maximal Shortest Synchronizing Word Length

Autor: Zantema, H., Don, H., Drewes, Frank, Martín-Vide, Carlos, Truthe, Bianca

Publikováno v: Drewes, F.; Martín-Vide, C.; Truthe, B. (ed.), Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings, pp. 249-260
Drewes, F.; Martín-Vide, C.; Truthe, B. (ed.), Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings, 249-260. Cham : Springer International Publishing
STARTPAGE=249;ENDPAGE=260;ISSN=0302-9743;TITLE=Drewes, F.; Martín-Vide, C.; Truthe, B. (ed.), Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings
Language and Automata Theory and Applications-11th International Conference, LATA 2017, Proceedings: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings, 249-260
STARTPAGE=249;ENDPAGE=260;TITLE=Language and Automata Theory and Applications-11th International Conference, LATA 2017, Proceedings
Language and Automata Theory and Applications ISBN: 9783319537320
LATA

It was conjectured by Černý in 1964 that a synchronizing DFA on n states always has a shortest synchronizing word of length at most (n−1) 2 (n−1)2, and he gave a sequence of DFAs for which this bound is reached. In 2006 Trahtman conjectured tha

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::80ea94c8415a6fe730451d5b91675846
https://hdl.handle.net/2066/173189

Lower bounds for synchronizing word lengths in partial automata

Autor: Michiel de Bondt, Hans Zantema, Henk Don

Publikováno v: arXiv, 2018:1801.10436. Cornell University Library
International Journal of Foundations of Computer Science, 30(1), 29-60. World Scientific
International Journal of Foundations of Computer Science, 30, 1, pp. 29-60
International Journal of Foundations of Computer Science, 30, 29-60

It was conjectured by \v{C}ern\'y in 1964, that a synchronizing DFA on $n$ states always has a synchronizing word of length at most $(n-1)^2$, and he gave a sequence of DFAs for which this bound is reached. Until now a full analysis of all DFAs reach

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dd10b57b950cb6cd7e894c33deed61ef
https://doi.org/10.48550/arxiv.1801.10436

A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA.

Autor: BÉAL, MARIE-PIERRE¹ beal@univ-mlv.fr, BERLINKOV, MIKHAIL V.² berlm@mail.ru, PERRIN, DOMINIQUE¹ perrin@univ-mlv.fr, Diekert, Volker, Nowotka, Dirk

Publikováno v: International Journal of Foundations of Computer Science. Feb2011, Vol. 22 Issue 2, p277-288. 12p. 3 Diagrams.