11 citations · 29 across the 12 of their papers we have counts for
11 papers · 1 filter
Synchronization of strongly connected partial DFAs and prefix codes
Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov +1
We study synchronizing partial DFAs, which extend the classical concept of synchronizing complete DFAs and are a special case of synchronizing unambiguous NFAs. A partial DFA is ca…
Synchronizing Random Almost-Group Automata
Mikhail V. Berlinkov, Cyril Nicaud
In this paper we address the question of synchronizing random automata in the critical settings of almost-group automata. Group automata are automata where all letters act as permu…
Preimage problems for deterministic finite automata
Mikhail V. Berlinkov, Robert Ferens, Marek Szykuła
Given a subset of states of a deterministic finite automaton and a word , the preimage is the subset of all states mapped to a state in by the action of . We study th…
Algebraic synchronization criterion and computing reset words
Mikhail Berlinkov, Marek Szykuła
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…
Testing for Synchronization
Mikhail V. Berlinkov
We consider the first problem that appears in any application of synchronizing automata, namely, the problem of deciding whether or not a given -state -letter automaton is sy…
On two Algorithmic Problems about Synchronizing Automata
Mikhail V. Berlinkov
Under the assumption , we prove that two natural problems from the theory of synchronizing automata cannot be solved in polynomial time. The first pr…
On the probability of being synchronizable
Mikhail V. Berlinkov
We prove that a random binary automaton with states is synchronizing with high probability and the asymptotic is exactly as conjectured in [Cameron, 2011]. W…
The Cerny Conjecture
Mikhail Berlinkov
The Černý conjecture (Černý, 1964) states that each n-state \san\ possess a \sw\ of length . From the other side the best upper bound for the \rl\ of n-state \sa\ known so…
Synchronizing Automata on Quasi Eulerian Digraph
Mikhail V. Berlinkov
In 1964 Černý conjectured that each -state synchronizing automaton posesses a reset word of length at most . From the other side the best known upper bound on the reset…
On Carpi and Alessandro conjecture
M. V. Berlinkov
The well known open Černý conjecture states that each \san with states has a \sw of length at most . On the other hand, the best known upper bound is cubic of . Rec…
Approximating the minimum length of synchronizing words is hard
M. V. Berlinkov
We prove that, unless , no polynomial algorithm can approximate the minimum length of \sws for a given \san within a constant factor.