An algorithm for recognizing the completeness of a set of words and dynamics of prohibitions.pdf Задачи о полноте множества слов и избегаемости запрещённых подслов бесконечными символьными последовательностями были впервые сформулированы в [1] и исследованы в [2-4]. Литературу можно посмотреть в [4, 5] в контексте более широкой области исследования, называемой «Combinatorics on words». Исследованию языков, определяемых заданием запрещённых подслов и иначе называемых в последние годы «антисловарями», посвящено большое число публикаций с указанием различных приложений. В частности, это задачи анализа и синтеза криптографических функций и символьных последовательностей, в которых важны информационные и сложностные характеристики, связанные с изучением взаимосвязи со свойствами их подфункций или подслов. Множество S слов (запретов) в алфавите A называется полным (или блокирующим ), если любая бесконечная последовательность букв из A не свободна от S, то есть содержит в качестве своего подслова хотя бы одно слово из S [1,2]. Подмножество T С S, T = (X1ai1,... ,Xmaim}, где m = |A|, образует тупиковую относительно S систему слов (TCC), если 1) все последние буквы слов в T различны (т.е. это все m букв алфавита A); 2) для всех i = 1,... ,m - 1 слово Xi есть суффикс слова Xi+1. Если в S существует TCC, то применение к ней Т-операции состоит в удалении в самом длинном слове Xmaim его последней буквы aim (если в ТСС самое длинное слово не единственно, то выбираем любое). Удобно считать, что если S = A, то есть S - это множество всех букв алфавита A, то Т-операция применима к S и её результатом является пустое множество. Сочетая Т-операцию сокращения множества S с двумя другими естественными операциями сокращения - удалением из S одного из двух одинаковых слов и удалением слова X, если в S содержится подслово слова X, получаем последовательность множеств, которая в силу конечности S стабилизируется: S ^ Si ^ S2 ^... ^ S*. Теорема 1. Приведённые операции инвариантны относительно свойства множества S быть полным. Их применение (в любом порядке) распознает полноту множества S: 1) либо S* = 0, и тогда S - полное множество; 2) либо S* = 0 и к S* неприменимы операции сокращения, и тогда S - неполное. Основанный на теореме алгоритм распознавания полноты прост, но этап проверки наличия в S тупиковой системы слов, к которой применима Т-операция, трудоёмок. Однако, в отличие от полиномиального алгоритма в [3], этот алгоритм позволяет работать со словами различной длины в множестве S и получить сокращённое множество S*, эквивалентное S. Представляет интерес более широкая постановка вопроса о сохранении свойства полноты при изменениях в S, а также то, насколько свойство устойчиво к «ошибкам», например удалению букв в словах или самих слов из S. Расширяя неполные множества и сужая полные, можно находить границы перехода и управлять динамикой изменения свойства полноты и избегаемости запретов S. В этой связи важно получить ответ на следующий вопрос: насколько велико может быть различие мощностей полных тупиковых (несокращаемых) множеств S, S С An? Например, как ведёт себя (по n при фиксированном m) функция f (m, n) = max |Si|/|S2|, где m = |A|, а максимум берётся по всем парам {S1, S2} полных тупиковых множеств, S1,S2 С An? Можно доказать, что эта функция не ограничена никакой константой. Более точные оценки её роста значительно прояснили бы структуру полных множеств слов.

Скачать электронную версию публикации