Source author record

Mikhail Berlinkov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory

Catalog footprint

Research overview

2works

1topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Algebraic synchronization criterion and computing reset words

We refine a uniform algebraic approach for deriving upper bounds on reset thresholds of synchronizing automata. We express the condition that an automaton is synchronizing in terms of linear algebra, and obtain upper bounds for the reset thresholds of automata with a short word of a small rank. The results are applied to make several improvements in the area. We improve the best general upper bound for reset thresholds of finite prefix codes (Huffman codes): we show that an $n$ -state synchronizing decoder has a reset word of length at most $O(n \log^3 n)$ . In addition to that, we prove that the expected reset threshold of a uniformly random synchronizing binary $n$ -state decoder is at most $O(n \log n)$ . We also show that for any non-unary alphabet there exist decoders whose reset threshold is in $\varTheta(n)$ . We prove the Černý conjecture for $n$ -state automata with a letter of rank at most $\sqrt[3]{6n-6}$ . In another corollary, based on the recent results of Nicaud, we show that the probability that the Černý conjecture does not hold for a random synchronizing binary automaton is exponentially small in terms of the number of states, and also that the expected value of the reset threshold of an $n$ -state random synchronizing binary automaton is at most $n^{3/2+o(1)}$ . Moreover, reset words of lengths within all of our bounds are computable in polynomial time. We present suitable algorithms for this task for various classes of automata, such as (quasi-)one-cluster and (quasi-)Eulerian automata, for which our results can be applied.

preprint2012arXiv

The Cerny Conjecture

The Černý conjecture (Černý, 1964) states that each n-state \san\ possess a \sw\ of length $(n-1)^2$ . From the other side the best upper bound for the \rl\ of n-state \sa\ known so far is equal to $\frac{n^3-n}6$ (Pin, 1983) and so is cubic (a slightly better though still cubic upper bound $\frac{n(7n^2+6n-16)}{48}$ has been claimed in Trahtman but the published proof of this result contains an unclear place) in $n$ . In the paper the Černý conjecture is reduced to a simpler conjecture. In particular, we prove Černý conjecture for one-cluster automata and quadratic upper bounds for automata closed to one-cluster automata. Our approach utilize theory of Markov chains and one simple fact from linear programming.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.