Информационная система "Конференции"

Вычислительные и информационные технологии в науке, технике и образовании

Усть-Каменогорск, Казахстан, 11-14 сентября 2003 года

Тезисы докладов

Сложность задач о полноте множества слов

Евдокимов А.А.

Институт математики им. С.Л.Соболева СО РАН (Новосибирск)

Пусть S- произвольное множество слов в конечном алфавите A и P(X) – множество всех подслов слова X или бесконечной последовательности в алфавите A (подслово длины m образуют любые m последовательных букв, m =1,2,3,…).
Скажем, что X свободно от S, или избегает множество S, если P(X)∩S=Ø. S называется полным, или блокирующим, если всякая бесконечная последовательность в алфавите A не свободна от S.

В теоретических и прикладных исследованиях часто возникает задача– распознать полноту данного множества «запрещенных» слов S, а в случае его полноты оценить мощность множества слов, свободных от S, или найти наибольшую длину L(S) свободного слова [2,4].

Автором был разработан алгоритм распознавания полноты множества слов S. Он основан на анализе циклической структуры подграфа графа де Брёйна порядка n и имеет трудоемкость O(|S|∙n), где n- наибольшая длина слова в S [1,3]. Анализ других известных алгоритмов, например, алгоритма пошагового сокращения множества S или перебора слов длины не более L(S)+1, имеет оценку сложности, которая экспоненциально зависит от n . Кроме того, имеет место следующяя теорема.

Пусть дано конечное множество слов S и натуральное число L.
Теорема. Задача распознавания существования свободного от S слова длины не менее L является NP-полной.

Таким образом, задача распознавания ограниченности множества слов,свободных от S, эффективно разрешима, а задача о локализации границы длин свободных слов уже NP-полна.

В докладе предполагается подробно рассмотреть и сравнить трудоемкость нескольких алгоритмов распознавания полноты конечных множеств S, заданных списком слов.

Работа поддержана грантом РФФИ 02-01-00939 и грантом Минобразования РФ Е02-6.0-250

ЛИТЕРАТУРА

1. Евдокимов А.А. Полные множества слов и их числовые характеристики // Методы дискретного анализа в исследовании экстремальных структур: Сб. науч. трудов Новосибирск: Ин-т математики СО АН СССР, 1983. Вып. 39. С.7-19.

2. Евдокимов А.А., Левин А.А. Графические модели и комбинаторика генетических и математических символьных последовательностей // Вычислительные технологии, Т.7, совместный выпуск, часть 2, 2002г. Вестник КазНУ, N4(32). С. 274-278.

3. Evdokimov A., Kitaev S. Crucial words and the complexity of some extremal problems for set of prohibited words. http://www.math.chalmers.se/Math/Research/Preprints/2001:64. 18p.

4. Choffrut C. Karhumaki J. Combinatorics of words// Handbook of formal languages. V.1: Words, language, grammar. Berlin: Springer, 1997. P.329-438.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]