Автомат с бесконечным деревом

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

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

Определение

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

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

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

Беги

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

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

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

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

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

условий

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

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

Литература

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