11 citations · 29 across the 12 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.FL2013
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…
cs.FL2013★ 7 cited
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…