TY - GEN
T1 - DFAs and PFAs with long shortest synchronizing word length
AU - De Bondt, Michiel
AU - Don, Henk
AU - Zantema, Hans
PY - 2017
Y1 - 2017
N2 - It was conjectured by Černý 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 reaching this bound was only given for n ≤ 4 and with bounds on the number of symbols for n ≤ 10 Here we give the full analysis for n ≤ 6 without bounds on the number of symbols. For PFAs on n ≤ 6 states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding (n-1)2 for n = 4, 5, 6. For arbitrary n we use rewrite systems to construct a PFA on three symbols with exponential shortest synchronizing word length, giving significantly better bounds than earlier exponential constructions.We give a transformation of this PFAto a PFAon two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation.
AB - It was conjectured by Černý 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 reaching this bound was only given for n ≤ 4 and with bounds on the number of symbols for n ≤ 10 Here we give the full analysis for n ≤ 6 without bounds on the number of symbols. For PFAs on n ≤ 6 states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding (n-1)2 for n = 4, 5, 6. For arbitrary n we use rewrite systems to construct a PFA on three symbols with exponential shortest synchronizing word length, giving significantly better bounds than earlier exponential constructions.We give a transformation of this PFAto a PFAon two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation.
UR - http://www.scopus.com/inward/record.url?scp=85026766357&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85026766357&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-62809-7_8
DO - 10.1007/978-3-319-62809-7_8
M3 - Conference contribution
AN - SCOPUS:85026766357
SN - 9783319628080
VL - 10396 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 122
EP - 133
BT - Developments in Language Theory - 21st International Conference, DLT 2017, Proceedings
PB - Springer/Verlag
T2 - 21st International Conference on Developments in Language Theory, DLT 2017
Y2 - 7 August 2017 through 11 August 2017
ER -