Комбинаторные свойства частичных слов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

§1 Существование длины взаимодействия

§2 Точные оценки в частных случаях

§3 Формулировка прямой и обратной задачи. Бланки и рас-становки

§4 Решение обратной задачи

§5 Решение исходной задачи 46II Статистические закономерности

§6 Идея алгоритма

§7 Количество расстановок с заданной характеристической рас-становкой

§8 Построение вспомогательных таблиц

§9 Анализ полученных результатов 63III Свойство взаимодействия локальных периодов

§10 Используемая техника

§11 Разрезы

§12 Алгоритм проверки наличия в расстановке специальнойподпоследовательности

§13 Модификации алгоритма

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

1. Thue A. Ùber 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., Karhumâki 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. Césari Y., Vincent M. Une caractérisation des mots périodiques // C. R. Acad. Sci. Paris. 1978. - Vol. 286.- Pp. 1175-1177.

10. Duval J.-P. Une caractérisation des fonctions périodiques // 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.