Комбинаторные свойства частичных слов

Символьные последовательности, или слова, представляют собой важный и популярный объект комбинаторных исследований. Задачи, связанные со словами, возникали в различных областях математики и другихнаук и привели к возникновению отдельного раздела дискретной математики, занимающейся изучением комбинаторных свойств слов. Историю комбинаторики слов принято отсчитывать от 1906 года, когда былаопубликована работа [1]. С тех пор комбинаторика слов плодотворно развивалась и к настоящему времени обрела четкие контуры и собственнуюбогатую проблематику. Имеющаяся литература весьма обширна. Уномянем здесь монографии [2−4], а также [5] и ряд других глав трехтомного"Справочника по формальным языкам". Частичные слова представляют собой естественное обобщение понятия обычного слова. Частичное слово — это обычное слово, в которомчасть букв по каким-то причинам отсутствует. Изучение комбинаторныхсвойств частичных слов «в явном виде» началось совсем недавно, в 1999 году, с работы [6]. Задачи, в которых возникают частичные слова, можно разделить надва типа. В задачах первого типа некоторая часть информации нам неважна (вне зависимости от того, доступна она или нет). Примером можетслужить задача поиска в тексте по шаблону, когда шаблон содержит символ (или символы) со значением «что угодно». В задачах второго типанекоторая часть информации для нас важна, но по каким-либо причинам недоступна. По имеющейся части информации и некоторым дополнительным условиям необходимо полностью восстановить информацию. Примером является задача восстановления фрагментов файлов, повреждённых при передаче или в результате порчи носителя. Очень интересными представляются также задачи молекулярной биологии (см. [7]), в частности, задача реконструкции нуклеотидных цепочек ДНК по частично расшифрованным фрагментам. в данной работе изучаются комбинаторные свойства частичных слов, связанные с локальной и глобальной периодичностью.

1. Thue A. Uber unendliche Zeichenreihen // Norske Vid. Selsk. Skr. 1. Math-Nat. Kl. — 1906. — Vol. 7. — Pp. 1−22.

2. Lothaire M. Combinatorics on Words. — Addison-Wesley, 1983.

3. Lothaire M. Algebraic combinatorics on Words. — Cambridge University Press, 2002.

4. Lothaire M. Applied combinatorics on Words. — Cambridge University Press, 2005.

5. Choffrut C., Karhumaki J. Combinatorics of words // Handbook of formal languages / Ed. by G. Rozenberg, A.Salomaa. — Springer, Berlin, 1997.-Vol. 1.

6. Berstel J., Boasson L. Partial words and a theorem of Fine and Wilf // Theor. Сотр. Sci. 1999. — Vol. 218. Pp. 135−141.

7. Head T., Paun G., Pixton D. Language theory and molecular genetics // Handbook of formal languages / Ed. by G. Rozenberg, A.Salomaa. — Springer, Berlin, 1997. Vol. 2.

8. Blanchet-Sadri F., Duncan S. Partial words and the critical factorization theorem // Journal of Combinatorial Theory, Series A. — 2005. — Vol. 109. Pp. 221−245.

9. Cesari Y., Vincent M. Une caracterisation des mots periodiques // C. R. Acad. Sci. Paris. 1978. — Vol. 286. Pp. 1175−1177.

10. Duval J.-P. Une caracterisation des fonctions periodiques // C. R. Acad Sci. Paris. ~ 1979. Vol. 289. — Pp. 185−187.

11. Blanchet-Sadri F., Wetzler N. D. Partial words and the critical factorization theorem revisited. — в печати.

12. Guibas L., Odlyzko A. Periods in strings // Journal of Combinatorial Theory, Series A. ~ 1981. Vol. 30. — Pp. 19−42.

13. Halava V., Harju Т., Ilie L. Periods and binary words // Journal of Combinatorial Theory, Series A. 2000. — Vol. 89. — Pp. 298−303.

14. Blanchet-Sadri F., Chriscoe A. Local periods and binary partial words: an algorithm // Theor. Сотр. Sci. 2004. — Vol. 314. — Pp. 401−419.

15. Blanchet-Sadri F., Chen C.-T. Periods and Binary Partial Words with Two Holes. — в печати.

16. Blanchet-Sadri F., Shirey B. Periods, Partial Words, and a Result of Guibas and Odlyzko. — в печати.

17. Blanchet-Sadri F. Primitive partial words // Discrete Applied Mathematics. 2005. — Vol. 148. — Pp. 195−213.

18. Blanchet-Sadri F., Anavekar A. R. Testing Primitivity on Partial Words. — в печати.

19. Blanchet-Sadri F. Codes, orderings and partial words // Theor. Сотр. Sci. 2004. — Vol. 329. — Pp. 177−202.

20. Blanchet-Sadri F., Moorefield M. Pcodes of Partial Words. — в печати.

21. Leupold P. Languages of partial words how to obtain them and what properties they have // Grammars. — 2004. — Vol. 7. — Pp. 179−192.

22. Fine N., Wilf H. Uniqueness theorem for periodic functions // Proc. Amer. Math. Soc.- 1965. Vol. 16. Pp. 109−114.

23. Constantinescu S., Ilie L. Generalised Fine and Wilf’s theorem for arbitrary number of periods // Theor. Comput. Sci. — 2005. — Vol. 339, no. 1. Pp. 49−60.

24. Castelli M. G., Mignosi F., Restivo A. Fine and Wilf’s theorem for three periods and a generalization of Sturmian words. // Theor. Comput. Sci. 1999. — Vol. 218, no. 1. — Pp. 83−94.

25. Justin J. On a paper by Castelli, Mignosi, Restivo. // Theoret. Inform. Appl. 2000. — Vol. 34. — Pp. 373−377.

26. Shur A. M., Gamzova Yu. V. Periods' interaction property for partial words // Proceedings of WORDS'03, 4th International Conference on Combinatorics on Words. 2003. — Pp. 75−82.

27. Шур A. M., Гамзова Ю. В. Частичные слова и свойство взаимодействия периодов // Изв. РАН. Серия матпем. — 2004. — Т. 68, № 2. — С. 199−222.

28. Гамзова Ю. В. Статистические закономерности взаимодействия периодов частичных слов // Российская конф ." Дискретный анализ и исследование операций": Тез. докл. — Новосибирск, Институт математики СО РАН, 2004. С. 82.

29. Гамзова Ю. В. Статистические закономерности взаимодействия периодов частичных слов // Дискретный анализ и исследование операций. Серия 1. 2004. — Т. 11, № 4.— С. 20−35.

30. Gamzova Yu. V. Infinite walks on the set of integers with gaps // Международная алгебраическая конф.: Тез.докл. — Екатеринбург, УрГУ, 2005. С. 195−196.

31. Гамзова Ю. В. Локально периодические бесконечные частичные слова // Изв. УрГУ. Серия компьютерные науки и информационные технологии, вып.1. — 2006. — Т. 43. — С. 5−21.