Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSlowly synchronizing DFAs of 7 states and maximal slowly synchronizing DFAs
138
0
0.0
(
0
)
Added by
Michiel de Bondt
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Michiel de Bondt
Ask ChatGPT about the research
No Arabic abstract
We compute all synchronizing DFAs with 7 states and synchronization length >= 29. Furthermore, we compute alphabet size ranges for maximal, minimal and semi-minimal synchronizing DFAs with up to 7 states.
rate research
Read More
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. In this paper, we investigate the role of the alphabet size. For each possible alphabet size, we count DFAs on $n le 6$ states which synchronize in $(n-1)^2 - e$ steps, for all $e < 2lceil n/2 rceil$. Furthermore, we give constructions of automata with any number of states, and $3$, $4$, or $5$ symbols, which synchronize slowly, namely in $n^2 - 3n + O(1)$ steps. In addition, our results prove v{C}ernys conjecture for $n le 6$. Our computation has led to $27$ DFAs on $3$, $4$, $5$ or $6$ states, which synchronize in $(n-1)^2$ steps, but do not belong to v{C}ernys sequence. Of these $27$ DFAs, $19$ are new, and the remaining $8$ which were already known are exactly the emph{minimal} ones: they will not synchronize any more after removing a symbol. So the $19$ new DFAs are extensions of automata which were already known, including the v{C}erny automaton on $3$ states. But for $n > 3$, we prove that the v{C}erny automaton on $n$ states does not admit non-trivial extensions with the same smallest synchronizing word length $(n-1)^2$.
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.
In this paper, we consider the transition complexity of regular languages based on the incomplete deterministic finite automata. A number of results on Boolean operations have been obtained. It is shown that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity result is similar to that of state complexity.
We prove the following theorem. Suppose that $M$ is a trim DFA on the Boolean alphabet $0,1$. The language $L(M)$ is well-ordered by the lexicographic order $slex$ iff whenever the non sink states $q,q.0$ are in the same strong component, then $q.1$ is a sink. It is easy to see that this property is sufficient. In order to show the necessity, we analyze the behavior of a $slex$-descending sequence of words. This property is used to obtain a polynomial time algorithm to determine, given a DFA $M$, whether $L(M)$ is well-ordered by the lexicographic order. Last, we apply an argument in cite{BE,BEa} to give a proof that the least nonregular ordinal is $omega^omega $.
We consider the problem {sc Max Sync Set} of finding a maximum synchronizing set of states in a given automaton. We show that the decision version of this problem is PSPACE-complete and investigate the approximability of {sc Max Sync Set} for binary and weakly acyclic automata (an automaton is called weakly acyclic if it contains no cycles other than self-loops). We prove that, assuming $P e NP$, for any $varepsilon > 0$, the {sc Max Sync Set} problem cannot be approximated in polynomial time within a factor of $O(n^{1 - varepsilon})$ for weakly acyclic $n$-state automata with alphabet of linear size, within a factor of $O(n^{frac{1}{2} - varepsilon})$ for binary $n$-state automata, and within a factor of $O(n^{frac{1}{3} - varepsilon})$ for binary weakly acyclic $n$-state automata. Finally, we prove that for unary automata the problem becomes solvable in polynomial time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
