Volume 21, No 1, 2014, P. 3–14

UDC 519.114
M. N. Vyalyi, R. A. Gimadeev
Separation of words by positions of subwords

We present lower bounds on complexity of separation of words by positions of subwords. In the case of subwords of length 1, we show that the bound is exact up to a constant factor. Applications to the problem of separation of words by automata are considered. 
Bibliogr. 6.

Keywords: subword, separation of words, cyclotomic polynomial, automaton.

Vyalyi Mikhail Nikolaevich 1
Gimadeev Renat Ajratovich 2

1. Dorodnicyn Computing Centre of RAS,
40 Vavilov St., 119333 Moscow, Russia
2. Moscow Institute of Physics and Technology,
9 Institutskiy Lane, 141700 Dolgoprudny, Russia
e-mail: vyalyi@gmail.com, renat.ariacas@gmail.com

 © Sobolev Institute of Mathematics, 2015