@inproceedings{ac58db8f3eca4a5cae136b82334fe25b,
title = "DFAs and PFAs with long shortest synchronizing word length",
abstract = "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 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.",
author = "{de Bondt}, M. and H. Don and H. Zantema",
year = "2017",
doi = "10.1007/978-3-319-62809-7_8",
language = "English",
isbn = "978-3-319-62808-0",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "122--133",
editor = "E. Charlier and J. Leroy and M. Rigo",
booktitle = "Developments in Language Theory",
address = "Germany",
note = "21st International Conference on Developments in Language Theory (DLT 2017), August 7-11, 2017, Liege, Belgium, DLT 2017 ; Conference date: 07-08-2017 Through 11-08-2017",
}