Synchronizing non-deterministic finite automata

Henk Don, Hans Zantema

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)
33 Downloads (Pure)

Samenvatting

In this paper, we show that every D3-directing CNFA can be mapped uniquely to a DFA with the same synchronizing word length. This implies that Černý’s conjecture generalizes to CNFAs and that any upper bound for the synchronizing word length of DFAs is an upper bound for the D3-directing word length of CNFAs as well. As a second consequence, for several classes of CNFAs sharper bounds are established. Finally, our results allow us to detect all critical CNFAs on at most 6 states. It turns out that only very few critical CNFAs exist.

Originele taal-2Engels
Pagina's (van-tot)307-328
Aantal pagina's22
TijdschriftJournal of Automata, Languages and Combinatorics
Volume23
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - 2018

Vingerafdruk Duik in de onderzoeksthema's van 'Synchronizing non-deterministic finite automata'. Samen vormen ze een unieke vingerafdruk.

Citeer dit