Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinding Short Synchronizing Words for Prefix Codes
78
0
0.0
(
0
)
Added by
Andrew Ryzhikov
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the problems of finding a shortest synchronizing word and its length for a given prefix code. This is done in two different settings: when the code is defined by an arbitrary decoder recognizing its star and when the code is defined by its literal decoder (whose size is polynomially equivalent to the total length of all words in the code). For the first case for every $varepsilon > 0$ we prove $n^{1 - varepsilon}$-inapproximability for recognizable binary maximal prefix codes, $Theta(log n)$-inapproximability for finite binary maximal prefix codes and $n^{frac{1}{2} - varepsilon}$-inapproximability for finite binary prefix codes. By $c$-inapproximability here we mean the non-existence of a $c$-approximation polynomial time algorithm under the assumption P $ e$ NP, and by $n$ the number of states of the decoder in the input. For the second case, we propose approximation and exact algorithms and conjecture that for finite maximal prefix codes the problem can be solved in polynomial time. We also study the related problems of finding a shortest mortal and a shortest avoiding word.
rate research
Read More
In [1], we introduced the weakly synchronizing languages for probabilistic automata. In this report, we show that the emptiness problem of weakly synchronizing languages for probabilistic automata is undecidable. This implies that the decidability result of [1-3] for the emptiness problem of weakly synchronizing language is incorrect.
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.
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 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 5$, and with bounds on the number of symbols for $n leq 12$. Here we give the full analysis for $n leq 7$, without bounds on the number of symbols. For PFAs (partial automata) on $leq 7$ states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding $(n-1)^2$ for $n geq 4$. Where DFAs with long synchronization typically have very few symbols, for PFAs we observe that more symbols may increase the synchronizing word length. For PFAs on $leq 10$ states and two symbols we investigate all occurring synchronizing word lengths. We give series of PFAs on two and three symbols, reaching the maximal possible length for some small values of $n$. For $n=6,7,8,9$, the construction on two symbols is the unique one reaching the maximal length. For both series the growth is faster than $(n-1)^2$, although still quadratic. Based on string rewriting, for arbitrary size we construct 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. Both PFAs are transitive. Finally, we show that exponential lengths are even possible with just one single undefined transition, again with transitive constructions.
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
