Synchronizing non-deterministic finite automata
From MaRDI portal
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 v{C}ern'y's conjecture generalizes to CNFAs and that the general upper bound for the length of a shortest D3-directing word is equal to the Pin-Frankl bound for DFAs. 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.
Recommendations
Cited in
(17)- Synchronizing finite automata with short reset words
- On synchronizing unambiguous automata
- Synchronizing generalized monotonic automata
- Distributed graph problems through an automata-theoretic Lens
- Careful synchronization of partial deterministic finite automata
- Introducing synchrony in fuzzy automata
- Using SAT solvers for synchronization issues in non-deterministic automata
- Distributed graph problems through an automata-theoretic lens
- Experiments with Synchronizing Automata
- Composition sequences and synchronizing automata
- Multitape NFA: Weak Synchronization of the Input Heads
- scientific article; zbMATH DE number 554484 (Why is no real title available?)
- SYNCHRONIZATION OF TWO INTERACTING FINITE AUTOMATA
- Synchronizing series-parallel deterministic finite automata with loops and related problems
- \(D_2\)-synchronization in nondeterministic automata
- Synchronization of finite automata
- Improved upper bounds on synchronizing nondeterministic automata
This page was built for publication: Synchronizing non-deterministic finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4623036)
