DFAs and PFAs with long shortest synchronizing word length

M. de Bondt, H. Don, H. Zantema

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)

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 languageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings
EditorsE. Charlier, J. Leroy, M. Rigo
Place of PublicationDordrecht
PublisherSpringer
Pages122-133
Number of pages12
ISBN (Electronic)978-3-319-62809-7
ISBN (Print)978-3-319-62808-0
DOIs
Publication statusPublished - 2017
Event21st International Conference on Developments in Language Theory (DLT 2017), August 7-11, 2017, Liege, Belgium - Liege, Belgium
Duration: 7 Aug 201711 Aug 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10396 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Developments in Language Theory (DLT 2017), August 7-11, 2017, Liege, Belgium
Abbreviated titleDLT 2017
CountryBelgium
CityLiege
Period7/08/1711/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

    de Bondt, M., Don, H., & Zantema, H. (2017). DFAs and PFAs with long shortest synchronizing word length. In E. Charlier, J. Leroy, & M. Rigo (Eds.), 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