Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSynchronizing non-deterministic finite automata
65
0
0.0
(
0
)
Added by
Henk Don
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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}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.
rate research
Read More
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 of the challenges is the size of the DPA, which often grows very fast in practice, and can reach double exponential size in the length of the LTL formula. In this paper we describe a single exponential translation from limit-deterministic Buchi automata (LDBA) to DPA, and show that it can be concatenated with a recent efficient translation from LTL to LDBA to yield a double exponential, enquote{Safraless} LTL-to-DPA construction. We also report on an implementation, a comparison with the SPOT library, and performance on several sets of formulas, including instances from the 2016 SyntComp competition.
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 reaching this bound was only given for $n leq 4$, and with bounds on the number of symbols for $n leq 10$. Here we give the full analysis for $n leq 6$, without bounds on the number of symbols. For PFAs the bound is much higher. For $n leq 6$ we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding $(n-1)^2$ for $n =4,5,6$. For arbitrary n we give a construction of 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.
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 $(n-1)^2$. We introduce the notion of aperiodically $1-$contracting automata and prove that in these automata all subsets of the state set are reachable, so that in particular they are synchronizing. Furthermore, we give a sufficient condition under which the v{C}erny conjecture holds for aperiodically $1-$contracting automata. As a special case, we prove some results for circular automata.
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 satisfactory results for automata with up to 100 states even if very modest computational resources are used. We compare our results with the ones obtained by the first author for exact synchronization, which is another version of synchronization studied in the literature, and draw some theoretical conclusions.
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 $mathcal{C}_n$ have switch count linear in $n$, we wonder whether synchronizing automata exist for which every synchronizing word has quadratic switch count. The answer is positive: we prove that switch count has the same complexity as synchronizing word length. We give some series of synchronizing automata yielding quadratic switch count, the best one reaching $frac{2}{3} n^2 + O(n)$ as switch count. We investigate all binary automata on at most 9 states and determine the maximal possible switch count. For all $3leq nleq 9$, a strictly higher switch count can be reached by allowing more symbols. This behaviour differs from length, where for every $n$, no automata are known with higher synchronization length than $mathcal{C}_n$, which has only two symbols. It is not clear if this pattern extends to larger $n$. For $ngeq 12$, our best construction only has two symbols.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
