Separating words by occurrences of subwords
M. Vyalyi, R. A. Gimadeev · Journal of Applied and Industrial Mathematics · 2014
We obtain some lower bounds for the complexity of word separation by occurrences of subwords. In the case of length 1 subwords, we show that the bound is exact up to a constant factor. Connection with the problem of separating words by automata is considered.