Автомат с бесконечным деревом - Infinite-tree automaton

В Информатика и математическая логика, автомат с бесконечным деревом это Государственный аппарат что имеет дело с бесконечным древовидные структуры. Это можно рассматривать как продолжение нисходящего конечные древовидные автоматы к бесконечным деревьям или как продолжение бесконечнословные автоматы к бесконечным деревьям.

Конечный автомат, работающий на бесконечном дереве, впервые был использован Майкл Рабин^[1] для доказательства разрешимости монадических логика второго порядка. Далее было замечено, что древовидные автоматы и логические теории тесно связаны, и это позволяет свести проблемы решения в логике к проблемам решения для автоматов.

Определение

Автоматы с бесконечным деревом работают над ${\displaystyle \Sigma }$-маркированные деревья. Есть много немного разных определений; вот один. A (недетерминированный) автомат с бесконечным деревом кортеж ${\displaystyle A=(\Sigma ,D,Q,q_{0},\delta ,F)}$ со следующими компонентами.

• ${\displaystyle \Sigma }$ это алфавит. Этот алфавит используется для обозначения узлов входного дерева.
• ${\displaystyle D\subset \mathbb {N} }$ - конечный набор разрешенных степеней ветвления входного дерева. Например, если ${\displaystyle D=\{2\}}$, входное дерево должно быть двоичным деревом, или если ${\displaystyle D=\{1,2,3\}}$, то каждый узел имеет 1, 2 или 3 потомка.
• ${\displaystyle Q}$ - конечный набор состояний; ${\displaystyle q_{0}}$ начальный.
• ${\displaystyle \delta :Q\times \Sigma \times D\rightarrow 2^{Q^{*}}}$ отношение перехода, которое отображает состояние автомата ${\displaystyle q\in Q}$, вводимая буква ${\displaystyle \sigma \in \Sigma }$, и степень ${\displaystyle d\in D}$ к набору ${\displaystyle d}$-наборы состояний.
• ${\displaystyle F\subseteq Q^{\omega }}$ является условием принятия.

Автомат с бесконечным деревом - это детерминированный если для каждого ${\displaystyle q\in Q}$, ${\displaystyle \sigma \in \Sigma }$, и ${\displaystyle d\in D}$, переходное соотношение ${\displaystyle \delta (q,\sigma ,d)}$ имеет ровно один ${\displaystyle d}$-пара.

Пробег

Интуитивно понятно, что запуск древовидного автомата на входном дереве присваивает состояния автомата узлам дерева таким образом, который удовлетворяет отношению перехода автомата. пробег древовидного автомата ${\displaystyle A}$ через ${\displaystyle \Sigma }$маркированное дерево ${\displaystyle (T,V)}$ это ${\displaystyle Q}$маркированное дерево ${\displaystyle (T_{r},r)}$ следующее. Предположим, что автомат достиг узла ${\displaystyle t}$ входного дерева и в настоящее время находится в состоянии ${\displaystyle q}$. Пусть узел ${\displaystyle t}$ быть помеченным ${\displaystyle \sigma \in \Sigma }$ и ${\displaystyle d(t)}$ быть степенью его ветвления. Затем автомат переходит к выбору кортежа ${\displaystyle (q_{1},...,q_{d(t)})}$ из набора ${\displaystyle \delta (q,\sigma ,d(t))}$ и клонирует себя в ${\displaystyle d(t)}$ копии. Для каждого ${\displaystyle 0<i\leq d(t)}$, одна копия автомата переходит в узел ${\displaystyle t.i}$ и меняет свое состояние на ${\displaystyle q_{i}}$. Это производит запуск, который ${\displaystyle Q}$маркированное дерево. Формально пробег ${\displaystyle (T_{r},r)}$ на входном дереве удовлетворяет следующим двум условиям.

• ${\displaystyle r(\epsilon )=q_{0}}$.
• Для каждого ${\displaystyle t\in T_{r}}$ с ${\displaystyle r(t)=q}$, существует ${\displaystyle (q_{1},...,q_{d(t)})\in \delta (q,V(t),d(t))}$ так что для каждого ${\displaystyle 0<i\leq d(t)}$, у нас есть ${\displaystyle t.i\in T_{r}}$ и ${\displaystyle r(t.i)=q_{i}}$.

Если автомат недетерминирован, на одном входном дереве может быть несколько разных прогонов; для детерминированных автоматов запуск уникален.

Условие приема

В бегах ${\displaystyle (T_{r},r)}$, бесконечный путь помечен последовательностью состояний. Эта последовательность состояний образует бесконечное слово над состояниями. Если все эти бесконечные слова принадлежат условию принятия ${\displaystyle F}$, то пробег принимая. Интересные условия приема Бючи, Рабин, Streett, Мюллер, и паритет. Если для входа ${\displaystyle \Sigma }$маркированное дерево ${\displaystyle (T,V)}$, существует принимающий прогон, тогда входное дерево принято автоматом. Набор всех принятых ${\displaystyle \Sigma }$помеченные деревья называются древовидным языком ${\displaystyle {\mathcal {L}}(A)}$ который признанный древовидным автоматом ${\displaystyle A}$.

Выразительная сила условий приема

Недетерминированные автоматы Мюллера, Рабина, Стритта и дерева четности распознают один и тот же набор языков деревьев и, следовательно, обладают одинаковой выразительной способностью. Но недетерминированные автоматы-деревья Бюхи строго слабее, т. Е. Существует язык деревьев, который может быть распознан Рабином. древовидный автомат, но не может быть распознан никаким древовидным автоматом Бюхи.^[2] (Например, не существует древовидного автомата Бюхи, распознающего множество ${\displaystyle \{a,b\}}$помеченные деревья, каждый путь которых имеет только конечное число ${\displaystyle a}$s, см., например, ^[3]Кроме того, детерминированные древовидные автоматы (Мюллера, Рабина, Стритта, четности, Бюхи, зацикливания) строго менее выразительны, чем их недетерминированные варианты. Например, не существует детерминированного древовидного автомата, который распознает язык двоичных деревьев, корень которых находится слева или правый ребенок отмечен ${\displaystyle a}$. Это резко контрастирует с автоматами на бесконечном слова, где недетерминированные Бюхи ω-автоматы обладают такой же выразительной силой, как и другие.

Языки недетерминированных автоматов Мюллера / Рабина / Стритта / дерева четности замкнуты относительно объединения, пересечения, проекции и дополнения.

Рекомендации

1. Рабин, М.О .: Разрешимость теорий и автоматов второго порядка на бесконечных деревьях,Труды Американского математического общества, т. 141. С. 1–35, 1969.
2. Рабин, М.О .: Слабо определимые отношения и специальные автоматы,Математическая логика и основы теории множеств1970. С. 1–23.
3. Онг, Люк, Автоматы, логика и игры (PDF), с. 92 (теорема 6.1)

• Вольфганг Томас (1990). «Автоматы на бесконечных объектах». В Ян ван Леувен (ред.). Формальные модели и семантика. Справочник по теоретической информатике. B. Эльзевир. С. 133–191. В частности: Часть II Автоматы на бесконечных деревьях, pp.165-185.
• А. Сауди и П. Бониццони (1992). «Автоматы на бесконечных деревьях и рациональное управление». В Морис Нива и Андреас Подельски (ред.). Древовидные автоматы и языки. Исследования в области компьютерных наук и искусственного интеллекта. 10. Амстердам: Северная Голландия. С. 189–200.