### Abstract

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.

Original language | English |
---|---|

Title of host publication | Developments in Language Theory |

Subtitle of host publication | 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings |

Editors | E. Charlier, J. Leroy, M. Rigo |

Place of Publication | Dordrecht |

Publisher | Springer |

Pages | 122-133 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-319-62809-7 |

ISBN (Print) | 978-3-319-62808-0 |

DOIs | |

Publication status | Published - 2017 |

Event | 21st International Conference on Developments in Language Theory (DLT 2017), August 7-11, 2017, Liege, Belgium - Liege, Belgium Duration: 7 Aug 2017 → 11 Aug 2017 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10396 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 21st International Conference on Developments in Language Theory (DLT 2017), August 7-11, 2017, Liege, Belgium |
---|---|

Abbreviated title | DLT 2017 |

Country | Belgium |

City | Liege |

Period | 7/08/17 → 11/08/17 |

## Fingerprint Dive into the research topics of 'DFAs and PFAs with long shortest synchronizing word length'. Together they form a unique fingerprint.

## Cite this

*Developments in Language Theory : 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings*(pp. 122-133). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10396 LNCS). Springer. https://doi.org/10.1007/978-3-319-62809-7_8