Separating Words by Occurrences of Subwords

摘要

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.