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

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Март 2019 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

Определение

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

• ${ displaystyle Sigma}$ это алфавит. Этот алфавит используется для обозначения узлов входного дерева.
• ${ Displaystyle D подмножество 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 substeq 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 (Т, В)}$ это ${ 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 дельта (д, сигма, d (т))}$ и клонирует себя в ${ displaystyle d (t)}$ копии. Для каждого ${ Displaystyle 0 <я Leq d (т)}$, одна копия автомата переходит в узел ${ displaystyle t.i}$ и меняет свое состояние на ${ displaystyle q_ {i}}$. Это производит запуск, который ${ displaystyle Q}$маркированное дерево. Формально пробег ${ displaystyle (T_ {r}, r)}$ на входном дереве удовлетворяет следующим двум условиям.

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

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

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

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

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

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

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

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

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