나무보행자동화

나무보행자동화(TWA)는 끈이 아닌 나무 구조를 다루는 유한 자동화의 일종이다.이 개념은 원래 아호와 울만이 제안한 것이다.^[1]

다음 기사는 나무를 걷는 오토마타를 다루고 있다.일반 트리 언어와 밀접한 관련이 있는 트리 자동화에 대한 다른 개념은 분기 자동화를 참조하십시오.

정의

모든 나무는 고정 문자 Ⅱ의 라벨이 있는 2진수로 가정한다.

비공식적으로, 나무 걷는 자동자(TWA) A는 입력 트리를 순차적으로 넘어가는 유한 상태 장치다.각 순간 A가 상태 q의 노드 v를 방문한다.상태 q, 노드 v의 라벨, 그리고 노드가 루트인지, 왼쪽 아이인지 오른쪽 아이인지 잎인지에 따라 A는 상태를 q에서 q'로 변경하고 v의 부모 또는 그 왼쪽이나 오른쪽 아이로 이동한다.TWA는 트리가 수용 상태에 들어가면 트리를 받아들이고, 트리가 거부 상태에 들어가거나 무한 루프(infinite loop)를 만들면 트리를 거부한다.스트링 오토마타와 마찬가지로 TWA는 결정론적이거나 비결정론적일 수 있다.

More formally, a (nondeterministic) tree-walking automaton over an alphabet Σ is a tuple A = (Q, Σ, I, F, R, δ) where Q is a finite set of states, its subsets I, F, and R are the sets of initial, accepting and rejecting states, respectively, and δ ⊆ (Q × { root, left, right, leaf } × Σ × { up, left, right } × Q) is the transition relation.

예

나무를 걷는 자동화의 간단한 예는 입력 트리에서 깊이 우선 검색(DFS)을 수행하는 TWA이다.The automaton ${\displaystyle A}$ has three states, ${\displaystyle Q=\{q_{0},q_{\mathit {left}},q_{\mathit {right}}\}}$. ${\displaystyle A}$ begins in the root in state ${\displaystyle q_{0}}$ and descends to the left subtree.그런 다음 나무를 재귀적으로 처리한다.$\{\backslash$$displaystyle$ $A}$이(가) 상태 $q{\displaystyle {}_{}}$ l ${\displaystyle {\mathit{e}}_{}}$ ${\displaystyle {\mathit{t}}_{}}$ ${\$의 노드$$ $v{\displaystyle }$ ${\displaystyle$ v$}$에 들어갈 때마다 v ${\displaystyle$ $v$$}$의 왼쪽 하위 트리가 방금 처리되었으므로$$ $v{\displaystyle }$ ${\displaystyle$ v$}$의 오른쪽 하위 트리로 진행됨을 의미한다$.$ $만약{\displaystyle }$ A$}$이 $노드$에 입력되면$$${\displaystyle }$$상태{\displaystyle }$ ${\displaystyle {q\mathit{}}_{}}$ r ${\displaystyle {\mathit{i}}_{}}$ ${\displaystyle {\mathit{g}}_{}}$ ${\displaystyle {\mathit{t}}_{}}$ ${\$의 v$$${\displaystyle v}$이(가) 있는 하위 트리 전체가 처리되었고$$ $A{\displaystyle }$ ${\displaystyle$A}이(가) $v{\displaystyle }${\$displaystyty v$}의 상위 항목으로 걸어가$$$$ ${\displaystyle {\mathit{ql}}_{}}$ ${\$ 상태로 변경됨을 의미한다.$v{\displaystyle }$ ${\$$displaystyle$ v}이(가$)$ 왼쪽 또는 오른쪽 하위 항목에 따라$$} 또는 ${\displaystyle {q\mathit{}}_{}}$ ${\displaystyle {\mathit{i}}_{}}$ ${\displaystyle {\mathit{g}}_{}}$ h {\$displaystyle$ q_${\mathit{right}}}}}}.$

특성.

가지를 치는 오토마타와는 달리, 나무로 걷는 오토마타는 분석하기 어렵다. 간단한 속성도 입증하기가 어렵다.다음 목록은 TWA와 관련된 몇 가지 알려진 사실을 요약한 것이다.

• Bojańczyk와 Colcombet에서 ^[2]보듯이 결정론적 TWA는 비결정론적 TWA보다 ${\displaystyle \mathit{엄격히}}$ 약하다(${\displaystyle \mathit{}}$ ${\displaystyle \mathit{TWA}}${ ${\displaystyle \mathit{TWA}}$ ${\$
• 결정론적 TWA는 보완 하에서 폐쇄된다(그러나 비결정론적 TWA의 경우 동일성이 유지되는지 여부는 알 수 없음).
• TWA가 인식하는 언어 집합은 정규 트리 언어(${\displaystyle \mathit{TWA}}$ ${\displaystyle ⊊}$ R ${\displaystyle \mathit{E}}$ ${\displaystyle \mathit{G}}$ ${\$에 엄격히 포함되어 있다.$$ 즉, 어떤 트리 걷기 자동화로도 인식되지 않는 정규 언어도 존재한다. 보자체지크 및 콜콤베트를 참조한다.^[3]

참고 항목

• 나무를 걷는 오토마타의 확장인 페블 오토마타

참조

외부 링크

• 미코와이 보자지크:나무로 걷는 오토마타.간단한 조사.