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

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

Abstract:
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 ¹
Gimadeev Renat Ajratovich ²
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