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 -