اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSlowly synchronizing DFAs of 7 states and maximal slowly synchronizing DFAs
138
0
0.0
(
0
)
تأليف
Michiel de Bondt
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 ro
le 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 unio
n 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
