Source author record

Mikhail V. 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 Data Structures and Algorithms Information Theory math.IT math.PR Other Computer Science

Catalog footprint

Research overview

4works

6topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Preimage problems for deterministic finite automata

Given a subset of states $S$ of a deterministic finite automaton and a word $w$ , the preimage is the subset of all states mapped to a state in $S$ by the action of $w$ . We study three natural problems concerning words giving certain preimages. The first problem is whether, for a given subset, there exists a word \emph{extending} the subset (giving a larger preimage). The second problem is whether there exists a \emph{totally extending} word (giving the whole set of states as a preimage)---equivalently, whether there exists an \emph{avoiding} word for the complementary subset. The third problem is whether there exists a \emph{resizing} word. We also consider variants where the length of the word is upper bounded, where the size of the given subset is restricted, and where the automaton is strongly connected, synchronizing, or binary. We conclude with a summary of the complexities in all combinations of the cases.

preprint2016arXiv

Highest Trees of Random Mappings

We prove the exact asymptotic $1-\left({\frac{2π}{3}-\frac{827}{288π}}+o(1)\right)/{\sqrt{n}}$ for the probability that the underlying graph of a random mapping of $n$ elements possesses a unique highest tree. The property of having a unique highest tree turned out to be crucial in the solution of the famous Road Coloring Problem as well as the generalization of this property in the proof of the author's result about the probability of being synchronizable for a random automaton.

preprint2014arXiv

On the Synchronization Rate for e-machines

It is known, that an $ε$ -machine is either exactly or asymptotically synchronizing. In the exact case, the observer can infer the current machine state after observing $L$ generated symbols with probability $1-a^L$ where $0 \leq a<1$ is a so-called synchronization rate constant. In the asymptotic case, the probability of the correct prediction the current machine state after observing $L$ generated symbols tends to $1$ exponentially fast as $1-b^L$ for $0<b<1$ and the infimum of such $b$ is a so-called prediction rate constant. Hence the synchronization and prediction rate constants serve as natural measures of synchronization for $ε$ -machines. In the present work we show how to approximate these constants in polynomial time in terms of the number of machine states.

preprint2012arXiv

Synchronizing Automata on Quasi Eulerian Digraph

In 1964 Černý conjectured that each $n$ -state synchronizing automaton posesses a reset word of length at most $(n-1)^2$ . From the other side the best known upper bound on the reset length (minimum length of reset words) is cubic in $n$ . Thus the main problem here is to prove quadratic (in $n$ ) upper bounds. Since 1964, this problem has been solved for few special classes of \sa. One of this result is due to Kari \cite{Ka03} for automata with Eulerian digraphs. In this paper we introduce a new approach to prove quadratic upper bounds and explain it in terms of Markov chains and Perron-Frobenius theories. Using this approach we obtain a quadratic upper bound for a generalization of Eulerian automata.

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.