Geodesic
Separation of words by positions of subwords
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 1, pp. 3-14 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, automaton.
Mots-clés : cyclotomic polynomial 
@article{DA_2014_21_1_a0,
     author = {M. N. Vyalyi and R. A. Gimadeev},
     title = {Separation of words by positions of subwords},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--14},
     year = {2014},
     volume = {21},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_1_a0/}
}
TY  - JOUR
AU  - M. N. Vyalyi
AU  - R. A. Gimadeev
TI  - Separation of words by positions of subwords
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 3
EP  - 14
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_1_a0/
LA  - ru
ID  - DA_2014_21_1_a0
ER  - 
%0 Journal Article
%A M. N. Vyalyi
%A R. A. Gimadeev
%T Separation of words by positions of subwords
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 3-14
%V 21
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2014_21_1_a0/
%G ru
%F DA_2014_21_1_a0
M. N. Vyalyi; R. A. Gimadeev. Separation of words by positions of subwords. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 1, pp. 3-14. http://geodesic.mathdoc.fr/item/DA_2014_21_1_a0/

[1] Leontev V. K., Khoshmand Asl M. R., “Kharakterizatsiya binarnykh slov podslovami”, Diskret. analiz i issled. operatsii. Ser. 1, 13:1 (2006), 65–76 | MR | Zbl

[2] Chandrasekkharan K., Vvedenie v analiticheskuyu teoriyu chisel., Mir, M., 1974, 188 pp. | MR

[3] Demaine E. D., Eisenstat S., Shallit J., Wilson D. A., “Remarks on separating words”, Descriptional complexity of formal systems, Lect. Notes Comput. Sci., 6808, 2011, 147–157 | DOI | MR | Zbl

[4] Karhumaki J., Puzynina S., Saarela A., “Fine and Wilf's theorem for $k$-Abelian periods”, Developments in language theory, Lect. Notes Comput. Sci., 7410, 2012, 296–307 | DOI | MR | Zbl

[5] Robson J. M., “Separating strings with small automata”, Inf. Process. Lett., 30 (1989), 209–214 | DOI | MR | Zbl

[6] Robson J. M., “Separating words with machines and groups”, Inform. Théor. Appl., 30 (1996), 81–86 | MR | Zbl