Дерево (теория автоматов)

В теории автоматов дерево — это особый способ представления древовидной структуры в виде последовательности натуральных чисел.

Например, каждый узел дерева представляет собой слово над множеством натуральных чисел ( ), что облегчает использование этого определения в теории автоматов .${\displaystyle \mathbb {N} }$

Дерево — это множество T ⊆ ^* такое, что если t . c ∈ T , причем t ∈ ^* и c ∈ , то t ∈ T и t . c ₁ ∈ T для всех 0 ≤ c ₁ < c . Элементы T называются узлами , а пустое слово ε ​​— (единственным) корнем T . Для каждого t ∈ T элемент t . c ∈ T является последователем t в направлении c . Число последователей t называется его степенью или арностью и обозначается как d ( t ) . Узел является листом , если у него нет последователей. Если каждый узел дерева имеет конечное число последователей, то он называется конечно , в противном случае — бесконечно ветвящимся деревом. Путь π — это подмножество T, такое что ε ∈ π и для каждого t ∈ T , либо t является листом, либо существует уникальный c ∈ такой, что t . c ∈ π. Путь может быть конечным или бесконечным множеством. Если все пути дерева конечны, то дерево называется конечным, в противном случае — бесконечным. Дерево называется полностью бесконечным, если все его пути бесконечны. Для заданного алфавита Σ Σ-меченое дерево — это пара ( T , V ), где T — дерево, а V : T → Σ отображает каждый узел T в символ в Σ. Меченое дерево формально определяет общеупотребимую структуру дерева терминов . Набор меченных деревьев называется языком деревьев .${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$

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

В случае ранжированных алфавитов определяется дополнительная функция Ar : Σ → . Эта функция связывает фиксированную арность с каждым символом алфавита. В этом случае каждый t ∈ T должен удовлетворять Ar ( V ( t )) = d ( t ). Деревья, удовлетворяющие этому свойству, называются ранжированными деревьями. Деревья, которые (не обязательно) удовлетворяют этому свойству, называются неранжированными .${\displaystyle \mathbb {N} }$

Например, приведенное выше определение используется в определении бесконечного древовидного автомата .

Пусть T = {0,1} ^* и Σ = { a , b }. Определим функцию маркировки V следующим образом: маркировка для корневого узла V (ε) = a и для каждого другого узла t ∈ {0,1} ^* маркировки для его последующих узлов V ( t .0) = a и V ( t .1) = b . Из рисунка ясно, что T образует (полностью) бесконечное бинарное дерево.

• Комон, Хьюберт; Доше, Макс; Жилерон, Реми; Жакмар, Флоран; Лужье, Денис; Лёдинг, Кристоф; Тисон, Софи; Томмаси, Марк (ноябрь 2008 г.). «Предварительные сведения». Методы и приложения древовидных автоматов (PDF) . Проверено 11 февраля 2014 г.