М. Н. Вялый, Р. А. Гимадеев, “О различении слов вхождениями подслов”, Дискретн. анализ и исслед. опер., 2014, том 21, выпуск 1,страницы 3

Эта публикация цитируется в 3 статьях

О различении слов вхождениями подслов

М. Н. Вялый^a, Р. А. Гимадеев^b

^a Вычислительный Центр РАН им. Дородницына, ул. Вавилова, 40, 119333 Москва, Россия
^b Московский физико-технический институт, Институтский пер., 9, 141700 Долгопрудный, Россия

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

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

УДК: 519.114

Статья поступила: 11.04.2013
Переработанный вариант: 02.07.2013