Том 21, номер 1, 2014 г., Стр. 3–14

УДК 519.114
М. Н. Вялый, Р. А. Гимадеев
О различении слов вхождениями подслов

Аннотация:
Получены нижние оценки сложности различения слов кратностями вхождений подслов с учётом позиции подслова в слове. Доказано, что в случае подслов длины 1 оценка оптимальна с точностью до мультипликативного множителя. Рассмотрена связь задачи различения слов вхождениями подслов с задачей различения слов автоматами.
Библиогр. 6.

Ключевые слова: подслово, различение слов, круговой многочлен, автомат.

Вялый Михаил Николаевич ¹
Гимадеев Ренат Айратович ²
1. Вычислительный Центр РАН им. Дородницына,
ул. Вавилова, 40, 119333 Москва, Россия
2. Московский физико-технический институт,
Институтский пер., 9, 141700 Долгопрудный, Россия
е-mail: vyalyi@gmail.com, renat.ariacas@gmail.com

Статья поступила 11 апреля 2013 г.
Исправленный вариант — 2 июля 2013 г.

Литература

[1] Леонтьев В. К., Хошманд Асл М. Р. Характеризация бинарных слов подсловами // Дискрет. анализ и исслед. операций. Сер. 1. - 2006. - Т. 13, № 1. - С. 65–76.

[2] Чандрасекхаран К. Введение в аналитическую теорию чисел. - М.: Мир, 1974. - 188 с.

[3] Demaine E. D., Eisenstat S., Shallit J., Wilson D. A. Remarks on separating words // Descriptional complexity of formal systems. - 2011. - P. 147-157. (Lect. Notes Comput. Sci.; Vol. 6808).

[4] Karhumaki J., Puzynina S., Saarela A. Fine and Wilf’s theorem for k-Abelian periods // Developments in language theory. - 2012. - P. 296-307. (Lect. Notes Comput. Sci.; Vol. 7410).

[5] Robson J. M. Separating strings with small automata // Inf. Process. Lett. - 1989. - Vol. 30. - P. 209–214.

[6] Robson J. M. Separating words with machines and groups // Inform. Théor. Appl. - 1996. - Vol. 30. - P. 81–86.