ﻻ يوجد ملخص باللغة العربية
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}ernys 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.
Controller synthesis for general linear temporal logic (LTL) objectives is a challenging task. The standard approach involves translating the LTL objective into a deterministic parity automaton (DPA) by means of the Safra-Piterman construction. One o
It was conjectured by v{C}erny in 1964, that a synchronizing DFA on $n$ states always has a shortest 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
A deterministic finite automaton is synchronizing if there exists a word that sends all states of the automaton to the same state. v{C}erny conjectured in 1964 that a synchronizing automaton with $n$ states has a synchronizing word of length at most
We approach the task of computing a carefully synchronizing word of optimum length for a given partial deterministic automaton, encoding the problem as an instance of SAT and invoking a SAT solver. Our experiments demonstrate that this approach gives
Instead of looking at the lengths of synchronizing words as in v{C}ernys conjecture, we look at the switch count of such words, that is, we only count the switches from one letter to another. Where the synchronizing words of the v{C}erny automata $ma