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