1 Введение 1
2 Определения и основные результаты 2
3 Алгебраические утверждения 5
4 Доказательство достаточности для выполнения свойства WELLDOC 7
5 Доказательство необходимости для выполнения свойства WELLDOC
Список литературы
Комбинаторика слов — это сравнительно молодая область дискретной математики и теоретической информатики, основным объектом которой являются конечные или бесконечные последовательности символов из конечного алфавита, называемые словами. Комбинаторика слов тесно связана с разными разделами науки как внутри математики и информатики, так и за их пределами. Среди областей применения комбинаторики слов следует особенно отметить теорию автоматов и формальных языков, а также алгоритмы на строках. В данной работе изучается свойство распределения факторов в морфическом слове, которое может применяться для генерирования псевдослучайных последовательностей.
В наше время множество алгоритмов различной сложности основаны на случайных алгоритмах: ни одна симуляция не обходится без случайных последовательностей, некоторые даже простые алгоритмы, такие как Quick sort, генерируют случайные числа для оптимальной работы. И естественным образом появляется необходимость в построении случайных последовательностей, однако сделать это не просто, ведь любой алгоритм в каком-то смысле можно просчитать наперед. Одним из самых простых примеров генераторов случайных последовательностей являются линейные конгруэнтные генераторы.
Определение 1. Будем называть линейным конгруэнтным генератором последовательность Zn+1= aZn+ c mod m,для некоторых a, c, m E N.
Однако они имеют несвойственный случайным последовательностям дефект, называющийся решетчатая структура: если рассмотреть множество из всех п подряд идущих чисел из генератора как подмножество Zn, то они будут покрываться семейством параллельных плоскостей, не покрывающих всю плоскость, как на рисунке1.
В статье [4], чтобы избавиться от этого дефекта, предлагается генерировать некоторое бесконечное слово wнад алфавитом Е, а так же |Е| линейных конгруэнтных генераторов Z(г'). Далее рассматривать последовательность, в которой мы в wзаме¬няем все вхождения i-ой буквы на числа в генераторе Z(г).
Определение 2. Пусть w = w0w1 • • • — бесконечное слово над алфавитом Е и Z(г) — линейные конгруэнтные генераторы. Рассмотрим f — функцию такую, что f (i) = |{j
в w. Тогда новым генератором будет Z (w)n= Zf (п).
Выбором слова w можно получить последовательность, у которой не будет дефекта решетчатой структуры. В статье [1] приводится достаточное условие для отсутствия решетчатой структуры, называемое WELLDOC. Условие заключается в следующем. Рассмотрим для каждого фактора и бесконечного слова w и для каждого модуля mмножество всех префиксов, которые заканчиваются вхождением и. Для выполнения условия требуется, чтобы для каждого набора из |Е| остатков по модулю mсуществовал префикс из этого множества такой, что с этим набором остатков совпадает набор остатков числа вхождений каждой буквы в этот префикс.
В данной работе рассматривается свойство WELLDOC для слов, получающихся как предел применения некоторого морфизма последовательно к некоторой букве и последующим ее образам; такие слова называются морфическими. Преимущество использования таких слов для построения генераторов состоит, в частности, в том, что такие слова можно очень быстро генерировать.
Основным результатом работы является критерий выполнения свойства WELLDOC для бинарных морфических слов в терминах матрицы соответствующего морфизма. А именно, показано, что для морфического бинарного слова свойство WELLDOC выполняется в том и только том случае, когда определитель матрицы морфизма равен ±1. Для небинарных морфических слов, порожденных примитив¬ными морфизмами, приводится другое условие: свойство WELLDOC выполняется в том и только том случае, когда определитель матрицы морфизма равен ±1 и векторы Парика всех возвратов к первой букве этого морфического слова порождают пространство Z|s|, что проверяется, например, методом Гаусса.
В следующем разделе будут приведены необходимые комбинаторные определения, а также формулировки всех основных результатов этой работы. Необходимые факты из алгебры приводятся в разделе 3. В разделе 4 мы покажем, что при заявленном условии свойство WELLDOC действительно будет выполняться, а в разделе5 докажем необходимость нашего условия.
