Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInfinite Synchronizing Words for Probabilistic Automata (Erratum)
135
0
0.0
(
0
)
Added by
Mahsa Shirmohammadi
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
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.
The probabilistic bisimilarity distance of Deng et al. has been proposed as a robust quantitative generalization of Segala and Lynchs probabilistic bisimilarity for probabilistic automata. In this paper, we present a characterization of the bisimilarity distance as the solution of a simple stochastic game. The characterization gives us an algorithm to compute the distances by applying Condons simple policy iteration on these games. The correctness of Condons approach, however, relies on the assumption that the games are stopping. Our games may be non-stopping in general, yet we are able to prove termination for this extended class of games. Already other algorithms have been proposed in the literature to compute these distances, with complexity in $textbf{UP} cap textbf{coUP}$ and textbf{PPAD}. Despite the theoretical relevance, these algorithms are inefficient in practice. To the best of our knowledge, our algorithm is the first practical solution. The characterization of the probabilistic bisimilarity distance mentioned above crucially uses a dual presentation of the Hausdorff distance due to Memoli. As an additional contribution, in this paper we show that Memolis result can be used also to prove that the bisimilarity distance bounds the difference in the maximal (or minimal) probability of two states to satisfying arbitrary $omega$-regular properties, expressed, eg., as LTL formulas.
We present an infinite series of $n$-state Eulerian automata whose reset words have length at least $(n^2-3)/2$. This improves the current lower bound on the length of shortest reset words in Eulerian automata. We conjecture that $(n^2-3)/2$ also forms an upper bound for this class and we experimentally verify it for small automata by an exhaustive computation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
