Synchronizing non-deterministic finite automata

Henk Don, Hans Zantema

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
32 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)307-328
Number of pages22
JournalJournal of Automata, Languages and Combinatorics
Volume23
Issue number4
DOIs
Publication statusPublished - 2018

Keywords

  • D3-directing
  • Non-deterministic finite automata
  • Černý conjecture

Fingerprint Dive into the research topics of 'Synchronizing non-deterministic finite automata'. Together they form a unique fingerprint.

Cite this