무한 나무 오토매틱

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않다. 보다 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주십시요. (2019년 3월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

컴퓨터 과학과 수학 논리학에서 무한 나무 자동화는 무한 나무 구조를 다루는 국가 기계다.하향식 유한 나무 오토마타를 무한 나무로 확장하거나 무한 나무로 무한 단어 오토마타를 확장한 것으로 볼 수 있다.

무한 나무 위를 달리는 유한 자동화는 마이클 라빈에^[1] 의해 처음으로 단색 2차 논리학의 결정성을 증명하기 위해 사용되었다.나무 오토마타와 논리 이론이 밀접하게 연결되어 있고, 논리의 의사결정 문제를 오토마타의 의사결정 문제로 축소할 수 있다는 것이 더욱 관찰되었다.

정의

무한 나무 오토마타는 $\sigma {\displaystyle \mathrm{}}$ ${\displaystyle \Sigma }$ 라벨이 붙은 나무에서 작동한다.많은 다른 정의들이 있다; 여기 하나 있다.(nondeterministic) 무한 나무 자동화는 다음과 같은 $구성{\displaystyle }$ 요소를 가진$$ 튜플 A${\displaystyle }$=${\displaystyle }$( ${\displaystyle \mathrm{\sigma }}$, ${\displaystyle D}$, ${\displaystyle Q}$, ${\displaystyle {q\mathrm{}}_{}}$, ${\displaystyle \Delta }$, F$){\displaystyle A=(\Sigma ,D,Q,q_{0},\delta ,F)$이다.

• ${\displaystyle \mathrm{\sigma }}$ ${\displaystyle \Sigma$}은$($는) 알파벳이다.이 알파벳은 입력 트리의 노드에 라벨을 붙이는 데 사용된다.
• ${\displaystyle D}$ ${\displaystyle \subset }$ ${\displaystyle N\mathbb{}}$ ${\$은(는) 입력 트리에서 허용되는 분기 도들의 유한 집합이다$$.예를 들어,${\displaystyle }D{\displaystyle }$= { ${\displaystyle 2}$}$${\$displaystyle D=\{2$ 입력 트리는 이진 트리여야 $하며{\displaystyle }$,${\displaystyle }$D${\displaystyle }$=${\displaystyle }${ ${\displaystyle 1}$,${\displaystyle 2}$, 3$}$ {\$displaystyle D=\{1$,2,3$\backslash \}\}$인 경우 각 노드는 1, 2, 3개의 자식 트리를 가져야 한다.
• ${\displaystyle Q}$ ${\displaystyle Q}$은(는) 유한 집합이며, $q{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$}은$($는) 초기 집합이다$$.
• ${\$$$$Q\times \Sigma \times D\rightarrow 2^{Q^{*}}}$ is a transition relation that maps an automaton state ${\displaystyle q\in Q}$, an input letter ${\displaystyle \sigma \in \Sigma }$, and a degree ${\displaystyle d\in D}$ to a set of ${\displaystyle d}$-tuples of states.
• ${\displaystyle F}$ ${\displaystyle \subseteq }$ ${\displaystyle {}^{}}$ ${\displaystyle {\Omega }^{}}$ ${\$은(는) 수용 조건이다$$.

An infinite-tree automaton is deterministic if for every ${\displaystyle q\in Q}$, ${\displaystyle \sigma \in \Sigma }$, and ${\displaystyle d\in D}$, the transition relation ${\displaystyle \delta (q,\sigma ,d)}$ has exactly one ${\displaystyle d}$-tuple.

달리다

직관적으로 입력 트리에서 트리 자동 실행은 자동 변환 관계를 만족하는 방식으로 트리 노드에 자동 상태를 할당한다.A bit more formally, a run of a tree automaton ${\displaystyle A}$ over a ${\displaystyle \Sigma }$-labeled tree ${\displaystyle (T,V)}$ is a ${\displaystyle Q}$-labeled tree ${\displaystyle (T_{r},r)}$ as follows.자동화가 입력 트리의 노드$$ $t{\displaystyle }$ ${\$$displaystyle t$$}$에 도달하여 현재 상태 $q{\displaystyle }$ ${\displaystyle$ $q$$}$에 있다고 가정해 보십시오$.$ $노드{\displaystyle }$ t ${\$$displaystyle$$$t}에 ${\displaystyle \in }$ { { $\$\$sigma$ \$in$ \$sigma \$in$$ } $및{\displaystyle }$ d$(t)$가 분기$$ degree.Then, the automaton proceeds by selecting a tuple ${\displaystyle (q_{1},...,q_{d(t)})}$ from the set ${\displaystyle \delta (q,\sigma ,d(t))}$ and cloning itself into ${\displaystyle d(t)}$ copies.각 < ( t) ${\displaystyle 0<i\leq d(t)}$에 대해 자동화의 한 복사본이 노드 $t{\displaystyle }$ . ${\displaystyle i.}$ i ${\displaystyty$ t$.i}$로 진행되며$$ 상태를 ${\displaystyle q_{}}$ i ${\$로 변경한다$.$$이렇게{\displaystyle }$ 하면 Q ${\displaystyle Q}$ -라벨$$ 트리가 생성된다.형식적으로 입력 트리의$$ 실행$({\displaystyle T_{}}$r , ${\displaystyle r}$) ${\displaystyle(T_{r}r)}$이(가) 다음 두 조건을 만족한다.

• ${\displaystyle r}$ (${\displaystyle ϵ}$ )${\displaystyle }$= ${\displaystyle {q\mathrm{}}_{}}$ 0 ${\$ r$(\epsilon )=q_{0$
• 그러한 모든 0<>;나는 d(t){0<, i\leq\displaystyle d(t)}≤, 우리는 t.을 가질 때마다 t 들어 r(t)과 ∈ Tr{\displaystylet\in T_{r}})q{\displaystyle r(t)=q},(q1..., qd(t))∈δ(q, V(t), d(t)){\displaystyle(q_{1},...,q_{d(t)})\in\delta(q,V(t),d(t))}존재하 . 나는 ∈${\displaystyle T_{}}$ ${\displaystyle r_{}}$ ${\$ 및 $r$ ( ${\displaystyle t}$. ${\displaystyle i}$)${\displaystyle }$= ${\displaystyle q_{}}$ i ${\$

자동이 비결정론적인 경우, 동일한 입력 트리에 여러 가지 다른 런이 있을 수 있다. 결정론적 자동화의 경우 런은 고유하다.

합격조건

실행$({\displaystyle T}$ ${\displaystyle r_{}}$, r${\displaystyle }$) ${\displaystyle (T_{r}r$}r$)\}$에서 무한 경로는 일련의 상태로 레이블이 지정된다.이 상태 순서는 상태 위에 무한한 단어를 형성한다.이 모든 무제한 단어가 $조건{\displaystyle }$ F$${\$displaystyle$ F$\}$에 속한다면 실행은 조건 F {\displaystyle F}에 동의하는 것이다.흥미로운 수용조건은 뷔치, 라빈, 스트리트, 뮬러, 패리티다.입력 $\sigma {\displaystyle \mathrm{}}$ ${\displaystyle \Sigma }$ -labeled$$ tree (${\displaystyle T}$, ${\displaystyle V}$) ${\displaystyle (T,V)}$의 경우$,$ 입력 트리가 자동에 의해 승인된다.모든 승인된 ${\displaystyle \Sigma }$ 레이블이$$ 있는 트리의 집합을 트리 $언어{\displaystyle \mathcal{}}$ L${\displaystyle }$( A${\displaystyle }$) ${\displaystyle${\$mathcal{L}(A)}$라고 하며, 트리$$ 자동 $A{\displaystyle }$ ${\displaystystyle A}$에 의해 인식된다$.$

수용 조건의 표현력

비결정론적 뮬러, 라빈, 스트리트, 패리티 트리 오토마타는 같은 세트의 트리 언어를 인식하므로 표현력이 동일하다.하지만 비결 정적임 Büchi 나무 오토 머터 엄격히, 즉는 라빈 나무 automaton지만 어떤 Büchi 나무 automaton에 의해 인정될 수 없인정 받을 수 있는 나무 언어를 존재한다는 것 더 약하다.[2](예를 들어{a, b}{\displaystyle\와 같이{a,b\}의 집합을 인식할 수 없Büchi 나무 automaton}이 내게 되는 모든 경로 하 나무 -labeled.s 미세하게 많은 $a{\displaystyle }$ ${\displaystyle a}$만 참조. 더 나아가 결정론적 트리 오토마타(Muller, Rabin, Streett, parity, Büchi, 루프)는 비결정적 변형에 비해 표현력이 엄격히 떨어진다.예를 들어, 루트가$${\$displaystyle$}로 표시된 왼쪽 또는 오른쪽 자식을 가진 이진수 나무의 언어를 인식하는 결정론적 트리 자동화는 없다$.$이것은 비결정론적인 Büchi Ω-automata가 다른 것과 같은 표현력을 가지고 있는 무한한 단어의 오토마타와는 뚜렷한 대조를 이룬다.

비결정론적 Muller/Rabin/Street/parity tree automata의 언어는 조합, 교차점, 투영 및 보완에 따라 폐쇄된다.

참조

• Wolfgang Thomas (1990). "Automata on Infinite Objects". In Jan van Leeuwen (ed.). Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 133–191. 특히: 무한 나무의 제2부 오토마타, 페이지.165-185.
• A. Saoudi and P. Bonizzoni (1992). "Automata on Infinite Trees and Rational Control". In Maurice Nivat and Andreas Podelski (ed.). Tree Automata and Languages. Studies in Computer Science and Artificial Intelligence. Vol. 10. Amsterdam: North-Holland. pp. 189–200.