Lower bounds for synchronizing word lengths in partial automata

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Uittreksel

It was conjectured by Černý in 1964, that a synchronizing DFA on nn states always has a synchronizing word of length at most (n−1)2(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≤5n≤5, and with bounds on the number of symbols for n≤12n≤12. Here we give the full analysis for n≤7n≤7, without bounds on the number of symbols.
For PFAs (partial automata) on ≤7≤7 states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding (n−1)2(n−1)2 for n≥4n≥4. Where DFAs with long synchronization typically have very few symbols, for PFAs we observe that more symbols may increase the synchronizing word length. For PFAs on ≤10≤10 states and two symbols we investigate all occurring synchronizing word lengths.
We give series of PFAs on two and three symbols, reaching the maximal possible length for some small values of nn. For n=6,7,8,9n=6,7,8,9, the construction on two symbols is the unique one reaching the maximal length. For both series the growth is faster than (n−1)2(n−1)2, although still quadratic.
Based on string rewriting, for arbitrary size we 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 PFA to a PFA on two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation. Both PFAs are transitive.
Finally, we show that exponential lengths are even possible with just one single undefined transition, again with transitive constructions.


TaalEngels
Pagina's29-60
Aantal pagina's32
TijdschriftInternational Journal of Foundations of Computer Science
Volume30
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 2019

Vingerafdruk

Synchronization

Trefwoorden

    Citeer dit

    @article{7319b9f09aad4c4fbcf10bef0728710a,
    title = "Lower bounds for synchronizing word lengths in partial automata",
    abstract = "It was conjectured by Čern{\'y} in 1964, that a synchronizing DFA on nn states always has a synchronizing word of length at most (n−1)2(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≤5n≤5, and with bounds on the number of symbols for n≤12n≤12. Here we give the full analysis for n≤7n≤7, without bounds on the number of symbols.For PFAs (partial automata) on ≤7≤7 states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding (n−1)2(n−1)2 for n≥4n≥4. Where DFAs with long synchronization typically have very few symbols, for PFAs we observe that more symbols may increase the synchronizing word length. For PFAs on ≤10≤10 states and two symbols we investigate all occurring synchronizing word lengths.We give series of PFAs on two and three symbols, reaching the maximal possible length for some small values of nn. For n=6,7,8,9n=6,7,8,9, the construction on two symbols is the unique one reaching the maximal length. For both series the growth is faster than (n−1)2(n−1)2, although still quadratic.Based on string rewriting, for arbitrary size we 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 PFA to a PFA on two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation. Both PFAs are transitive.Finally, we show that exponential lengths are even possible with just one single undefined transition, again with transitive constructions.",
    keywords = "careful synchronization, conjecture, DFA, ern{\'y}, PFA",
    author = "{de Bondt}, M. and H.M. Don and Hans Zantema",
    year = "2019",
    doi = "10.1142/S0129054119400021",
    language = "English",
    volume = "30",
    pages = "29--60",
    journal = "International Journal of Foundations of Computer Science",
    issn = "0129-0541",
    publisher = "World Scientific",
    number = "1",

    }

    Lower bounds for synchronizing word lengths in partial automata. / de Bondt, M.; Don, H.M.; Zantema, Hans.

    In: International Journal of Foundations of Computer Science, Vol. 30, Nr. 1, 2019, blz. 29-60.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    TY - JOUR

    T1 - Lower bounds for synchronizing word lengths in partial automata

    AU - de Bondt,M.

    AU - Don,H.M.

    AU - Zantema,Hans

    PY - 2019

    Y1 - 2019

    N2 - It was conjectured by Černý in 1964, that a synchronizing DFA on nn states always has a synchronizing word of length at most (n−1)2(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≤5n≤5, and with bounds on the number of symbols for n≤12n≤12. Here we give the full analysis for n≤7n≤7, without bounds on the number of symbols.For PFAs (partial automata) on ≤7≤7 states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding (n−1)2(n−1)2 for n≥4n≥4. Where DFAs with long synchronization typically have very few symbols, for PFAs we observe that more symbols may increase the synchronizing word length. For PFAs on ≤10≤10 states and two symbols we investigate all occurring synchronizing word lengths.We give series of PFAs on two and three symbols, reaching the maximal possible length for some small values of nn. For n=6,7,8,9n=6,7,8,9, the construction on two symbols is the unique one reaching the maximal length. For both series the growth is faster than (n−1)2(n−1)2, although still quadratic.Based on string rewriting, for arbitrary size we 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 PFA to a PFA on two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation. Both PFAs are transitive.Finally, we show that exponential lengths are even possible with just one single undefined transition, again with transitive constructions.

    AB - It was conjectured by Černý in 1964, that a synchronizing DFA on nn states always has a synchronizing word of length at most (n−1)2(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≤5n≤5, and with bounds on the number of symbols for n≤12n≤12. Here we give the full analysis for n≤7n≤7, without bounds on the number of symbols.For PFAs (partial automata) on ≤7≤7 states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding (n−1)2(n−1)2 for n≥4n≥4. Where DFAs with long synchronization typically have very few symbols, for PFAs we observe that more symbols may increase the synchronizing word length. For PFAs on ≤10≤10 states and two symbols we investigate all occurring synchronizing word lengths.We give series of PFAs on two and three symbols, reaching the maximal possible length for some small values of nn. For n=6,7,8,9n=6,7,8,9, the construction on two symbols is the unique one reaching the maximal length. For both series the growth is faster than (n−1)2(n−1)2, although still quadratic.Based on string rewriting, for arbitrary size we 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 PFA to a PFA on two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation. Both PFAs are transitive.Finally, we show that exponential lengths are even possible with just one single undefined transition, again with transitive constructions.

    KW - careful synchronization

    KW - conjecture

    KW - DFA

    KW - erný

    KW - PFA

    UR - http://www.scopus.com/inward/record.url?scp=85062488392&partnerID=8YFLogxK

    U2 - 10.1142/S0129054119400021

    DO - 10.1142/S0129054119400021

    M3 - Article

    VL - 30

    SP - 29

    EP - 60

    JO - International Journal of Foundations of Computer Science

    T2 - International Journal of Foundations of Computer Science

    JF - International Journal of Foundations of Computer Science

    SN - 0129-0541

    IS - 1

    ER -