Реферат: Структура графа состояний клеточных автоматов определённого типа
верно равенство:
,
где 
―одна из последовательностей «нулевого» дерева на n-ном ярусе (сумма в поле 
) (Следует из теоремы 2.1).
Используя полученное соотношение можно достроить любое дерево до дерева изоморфного «нулевому».
§3 ACS-автомат
§3.1 Постановка задачи
В данной работе рассматривается клеточный автомат (одномерный), функционирование которого осуществляется по следующим правилам:
Дана полоска 1
n (сам автомат), все клетки, которой находятся в состояниях «0» и «1». Изменение состояния клетки определяется следующим образом: данная клетка переходит в состояние «1», если её соседи находятся в разных состояниях, и в «0»,если её соседи находятся в одинаковых состояниях. Клетки, находящиеся по краям переходят в то же состояние, которое было у единственной соседней клетки в предыдущий момент времени.
По полоске длины n будем определять вектор 
, где 
:
Рассмотрим множество 
и отображение 
такое, что
(здесь и ниже 
– операция сложения по modp=2, т.е. операция сложения в поле Z2 ).
Будем рассматривать граф состояний 
, для которого 
. Основной целью исследования является изучение структуры графа .
Для начала рассмотрим некоторые определения и обозначения, которые будут использоваться в дальнейшем в работе:
· Ориентированное дерево — это ориентированный граф без циклов, в котором из каждой вершины, кроме одной, называемой корнем ориентированного дерева, выходит ровно одно ребро (более подробно структуры дерева будет определена позже).
· m-й ярус – множество вершин дерева, находящихся на расстоянии m от корня.
· Частичный порядок на вершинах: 
, если вершины u и v различны и вершина u лежит на единственном элементарном пути, соединяющем вершиной v с корнем дерева.
· Корневое поддерево с корнем v — подграф 
.
· Множество 
назовем множеством висячих вершин графа 
.
§3.2 Краткий обзор предыдущих результатов
В прошлом году на ряде конференций (см. Используемые источники) была представлена работа по клеточным автоматам, в которой был исследован частный случай линейного оператора и найдены высоты деревьев для последовательностей, состоящих из 2n -1 элементов. В ней были представлены следующие утверждения, которые будут использоваться в дальнейшем:
Утверждение 3.2.1
.
Утверждение 3.2.2
1. 
;
2. 
, причем 
3. 
;
4. 
.
Утверждение 3.2.3
; 
и 
.
Предисловие