Структура графа состояний клеточных автоматов определённого типа

Рефераты / Экономико-математическое моделирование / Структура графа состояний клеточных автоматов определённого типа

Теорема 3.4.0

Вершина является висячей тогда и только тогда, когда n – нечётное и выполняется условие:

Доказательство:

Пусть у нас есть последовательности и ="images/referats/1519/image131.gif">

Тогда Но тогда .

Но по условию , т.е. для того чтобы вершина была висячей необходимо и достаточно, чтобы , т.е.

Теорема полностью доказана.

Теорема 3.4.1

Если длина последовательности кратна двум, то граф Gφ ― дизъюнктное объединение циклов.

Доказательство:

Воспользуемся тем, что дерево, притягиваемое каждой точкой каждого цикла, изоморфно нулевому дереву. Рассмотрим нулевое дерево. Его высота при n=2k равна нулю. Это следует из того, что , но m=2s+1, противоречие. Теорема полностью доказана.

Теорема 3.4.2

Если длину последовательности представить в виде pk(2l)-1, (p,l)=1, тогда pk есть высота «нулевого» дерева.

Доказательство:

Для начала докажем следующие леммы.

Лемма 1

– висячая вершина причем, .

Рис. 3.4.1 Пример для p = 5.

Доказательство леммы 1:

Для начала рассмотрим шахматную раскраску таблицы (2pk-1)(pk+1), строки которой есть последовательности , , …, (см. рис.). Тогда числа, стоящие на закрашенных позициях равны 0.

Остальные координаты образуют треугольник Паскаля с вершиной в 1 (см. пример на рис. 3.4.1 для p = 5). Тогда т.к. , то:

при этом (все значения биноминальных коэффициентов берутся по модулю p, так как мы рассматриваем вектор в пространстве )

Замечание:

Здесь и ниже, все многочлены рассматриваются над полем

Докажем, что

Действительно, т.к. (т.к. ), то: .

Откуда , ч.т.д.

Замечание

Висячесть вершины следует из теоремы 3.4.0

Следствие

– висячая вершина причем, .

Для доказательства домножим элементы рассмотренного выше треугольник Паскаля на i и в силу простоты p получим требуемое.

Лемма 2

Вершина н вида:

является висячей при условии, что число последовательностей вида , где не кратно p, причем .

Доказательство леммы 2:

Из теоремы 3.4.0, вершина является висячей при n нечётном и выполнении условия:

Таким образом, при подстановке соответствующих значений получим:

, где .

Таким образом, вершина вида:

является висячей при условии, что число конструкций вида , где m=1 либо (p-1), не кратно p. Вторая часть леммы следует из следствия леммы 1, причем, как и в лемме 1, Лемма доказана.

Приступим теперь к доказательству основной теоремы. Из леммы 1 следует, что высота дерева при равна pk, из леммы 2 следует, что если высота дерева при равна высоте дерева при и, при условии, что (l,p)=1.

Теорема полностью доказана.

§4 Структура графа состояний оператора взятия разностей

Введение

В данном параграфе рассматривается структура графа состояний Gw оператора взятия разностей (см. [1]), который определяется следующим образом:

В ([1]) w был рассмотрен только над Z2, в этом параграфе оператор взятия разностей будет рассмотрен над полем Zp. Оператор взятия разностей используется для анализа сложности функций (см. [1]).

На основе результатов параграфа 2 (теоремы 2.2, 2.3), для анализа структуры графа состояний оператора w достаточно определить высоту нулевого дерева, тем самым будут определена высота дерева притягиваемого каждой точкой каждого цикла графа Gw (теорема 2.3).

Теорема 4.1

Если , то наименьший период функции (mod p) по i равен pk.