M. N. Vyalyi, R. A. Gimadeev, “Separation of words by positions of subwords”, Diskretn. Anal. Issled. Oper., 2014, Volume 21, Issue 1,Pages <nobr>3

This article is cited in 3 papers

Separation of words by positions of subwords

M. N. Vyalyi^a, R. A. Gimadeev^b

^a Dorodnicyn Computing Centre of RAS, 40 Vavilov St., 119333 Moscow, Russia
^b Moscow Institute of Physics and Technology, 9 Institutskiy Lane, 141700 Dolgoprudny, Russia

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.

UDC: 519.114

Received: 11.04.2013
Revised: 02.07.2013