• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Separating words by occurrences of subwords

Journal of Applied and Industrial Mathematics. 2014. Vol. 8. No. 2. P. 293-299.
Vyalyi M., Gimadeev R.

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.