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

По теореме 3.3.2.1

, где с корнем .

Возьмем последовательность

длиной ;

заметим, что тогда:

(в связи с симметрией относительно )

Но тогда:

Высота дерева при n=2^n-1 равна высоте дерева при n=3×2^n-1. В связи с симметрией относительно

, мы получаем:

Высота дерева при n=2ⁿ⁺¹+2^n-1-1 равна высоте дерева при n=3×2^n-1-1.

Таким образом, мы получаем, что если представить длины последовательности в виде:

, то 2-1^k Ї высота дерева.

Теорема доказана.

§3.4 Структура G_j при p¹2

Введение

В параграфе 2 мы рассматривали структуру графа состояний для произвольного линейного оператора над Z_p. В данном параграфе пойдет речь о структуре графа G_j определенного в параграфе 3.1. По аналогии со случаем p=2, по состоянию числовой полоски длины n (т.е. самого автомата с состояниями 0,1,..p-1) будем определять вектор

, и рассматривать такое, что:

Все остальные основные определения вводятся аналогичным образом, как и в случае p=2, основным предметом исследования является структура графа G_j.

Одним из важных свойств оператора j является его аддитивность:

которая следует из линейности оператора j.

В предыдущем параграфе было доказано утверждение о том, что для произвольного линейного оператора y «нулевое» дерево – p-нарное дерево с точностью до петли в корне (0,0..,0) (теорема 2.2). В данном параграфе будет определена высота нулевого дерева, тем самым будут определена высота дерева притягиваемого каждой точкой каждого цикла графа G_j (теорема 2.3).

Теорема 3.4.0

Вершина

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

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

Пусть у нас есть последовательности

и

Тогда

Но тогда .

Но по условию

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

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

Теорема 3.4.1

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

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

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

, но m=2s+1, противоречие. Теорема полностью доказана.

Теорема 3.4.2

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

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

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

Лемма 1

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

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

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

Для начала рассмотрим шахматную раскраску таблицы (2p^k-1)(p^k+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 следует, что высота дерева при

равна p^k, из леммы 2 следует, что если высота дерева при равна высоте дерева при и, при условии, что (l,p)=1.

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

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

Введение

В данном параграфе рассматривается структура графа состояний G_w оператора взятия разностей

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

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