트리 변환기

이론 컴퓨터 과학과 공식 언어 이론에서, 나무 변환기(TT)는 나무를 입력하여 출력을 생성하는 추상적인 기계다. 일반적으로 다른 나무들은 있지만 단어나 다른 구조를 생산하는 모델은 존재한다.대략적으로 말하면, 트리 변환기는 워드 변환기가 워드 오토마타를 확장하는 것과 같은 방식으로 트리 오토마타를 확장한다.

단어 대신 트리 구조를 조작하면 TT는 형식 또는 자연 언어의 구문 방향 변환을 모델링할 수 있다.그러나 TT는 알고리즘의 복잡성, 폐쇄 특성 등의 측면에서 단어 상대자들만큼 예의 바르게 행동하지 않는다.특히 주요 수업은 대부분 구성상 휴강하지 않고 있다.

트리 변환기의 주요 클래스는 다음과 같다.

하향식 트리 변환기(TOP)

TOP T는 다음과 같은 튜플(Q, ,, ,, I, Δ)이다.

• Q는 상태 집합인 유한한 집합이다.
• σ은 입력 알파벳이라 불리는 유한 순위 알파벳이다.
• γ은 출력 알파벳이라 불리는 유한 순위 알파벳이다.
• I는 Q의 하위 집합이며 초기 상태 집합이다.
• ${\displaystyle \delta }$ is a set of rules of the form ${\displaystyle q(f(x_{1},\dots ,x_{n}))\to u}$, where f is a symbol of Σ, n is the arity of f, q is a state, and u is a tree on Γ and ${\displaystyle Q\times \mathrm{1..}}$$n[\displaystyle$$n$ 그러한 쌍은 무효가 된다.

의미론에 대한 규칙과 직관의 예

예를 들어.

${\displaystyle q(f(x_{1},\reason,x_{3})\to g(a,q'(x_{1}), h(q')(x_{3})}}$

규칙 - 한 쌍$({\displaystyle q}$, x ${\displaystyle i_{}}$) ${\displaystyle(q,x_{i})$ 대신$$ $x_{i}}$를 관습적으로 쓰는 규칙이며,$$ 직관적인 의미론은 q의 작용에 따라 f가 뿌리에 있는 트리와 세 명의 자식들이 변형된다는 것이다.

${\displaystyle g(a,q'(x_{1}), h(q")(x_{3})}}$

여기서 $q{\displaystyle {}^{}}$ ${\displaystyle \prime ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$) ${\displaystyle q''(x_$${1$$})$과 $q{\displaystyle {}^{}}$ $x_$3$})$을 각각 첫 번째 아이에$$ $q{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$을(를) 적용하고 $q{\displaystyle {}^{}}$ ${\displaystyle {″}^{}}$ ${\$을(으)로$$ 대체한다$$.

용어 재작성으로서의 의미론

변환기 T의 각 상태와 T 자체의 의미론은 입력 트리( ()와 출력 트리( () 사이의 이진 관계다.

의미론을 공식적으로 정의하는 방법은 $\Delta {\displaystyle }$ ${\displaystyle \delta }$을(를) 용어 재작성 시스템으로 보는 것이다. 단, 우측에 통화 내용이 $q{\displaystyle }$( x ${\displaystyle i_{}}$) ${\displaysty q(x_{i$ 형식으로 기록되면, Δ {\displaysty \delta }을(으)를 참조한다.그러면 상태 q의 의미론${\displaystyle }$[ [${\displaystyle q}$ ${\displaystyle ]}$ ${\displaystyle [\![q]\]}$이(가) 제공된다.

$[\displaystyle [\![q]\!]=\{u\mapsto v\mid u{\text}는 }}\Sigma,\ v{\text{\text{}}}}}}}}}\Gamma {\text{}, }q(u)\to _{\delta }^{*v\}}}}}}}에 있는 트리.$

T의 의미론은 그 초기 상태의 의미론의 결합으로 정의된다.

$[\displaystyle [\![T]\]=\bigcup _{q\in I}[\]\!]}$

결정론과 영역

나무 오토마타와 마찬가지로 Δ의 두 규칙이 동일한 좌측을 공유하지 않고, 최대 하나의 초기 상태가 있는 경우 TOP는 결정론적(약칭 DTOP)이라고 한다.이 경우, DTOP의 의미론들은 각 DTOP 주의 의미론처럼 입력 트리( ()에서 출력 트리( ()에 이르는 부분적인 기능이다.

변환기의 영역은 그 의미론의 영역이다.마찬가지로 변환기의 이미지는 의미론적 이미지다.

DTOP의 속성

• DTOP는 결합에 의해 닫히지 않는다. 이것은 이미 결정론적 단어 변환기의 경우다.
• DTOP의 도메인은 일반 트리 언어다.또한 도메인은 초기 DTOP 크기의 결정론적 하향식 트리 자동(DTTA)으로 인식할 수 있다.^[1]

DTOP 규칙의 왼쪽 측면이 DTTA와 동일하다는 점을 고려할 때 도메인이 DTTA를 인식할 수 있다는 것은 놀라운 일이 아니다.As for the reason for the exponential explosion in the worst case (that does not exist in the word case), consider the rule ${\displaystyle q(f(x_{1},x_{2}))\to g(p_{1}(x_{1}),p_{2}(x_{1}),p_{3}(x_{2}))}$. In order for the computation to suc두 아이 모두 성공해야 한다.즉, 오른쪽 아이는 $p{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$의 영역에 있어야 한다는 뜻$.$ 왼쪽 아이에 대해서는 ${\displaystyle {p\mathrm{}}_{}}$ 1 ${\$1}와 ${\displaystyle {p\mathrm{}}_{}}$ $2{\displaystyle {}_{}}$ ${\$ 일반적으로 하위 트리를 복사할 수 있으므로, 실행 중 하나의 하위 트리를 여러 상태로 평가할 수 있다$.$DTTA와는 달리 결정론그러므로 DTOP의 영역을 인식하는 DTTA의 구축은 상태 집합을 고려해야 하며, 그 도메인들의 교차점, 즉 지수화를 계산해야 한다.선형 DTOP의 특별한 경우, 즉 각 ${\displaystyle x_{}}$ i ${\$가 각 규칙의 오른쪽에 최대 한 번 나타나는$$ DTOP의 경우 시공은 시공간적으로 선형이다.

• DTOP의 이미지는 일반 트리 언어가 아니다.

$변환기{\displaystyle }$ 코드화 f${\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$→ ${\displaystyle g}$( ${\displaystyle x}$, ${\displaystyle x}$) ${\displaystyle f(x)\to g(x,x$ 즉, 입력의 하위 항목을 복제하는 변환기를 고려하십시오.p가 ID를 인코딩하는 규칙 ${\displaystyle q({}_{}}$( ${\displaystyle {x\mathrm{}}_{}}$ 1${\displaystyle }$)${\displaystyle }$→ g${\displaystyle }$(${\displaystyle x}$ ${\displaystyle {1\mathrm{}}_{}}$)${\displaystyle }$, p${\displaystyle }$( ${\displaystyle x}$ ${\displaystyle {1\mathrm{}}_{}}$)${\displaystyle q(f(x_{1})\to g(x_{1}),p(x_{1})}$에 의해 쉽게 수행된다$.$그러면, 입력의 첫 번째 아이에 대한 어떠한 제한도 없이, 이미지는 고전적인 비정규 트리 언어다.

• 그러나 DTOP의 도메인은 일반 트리 언어로 제한될 수 없다.즉, DTOP T와 언어 L을 고려할 때 $일반적$으로 T${\displaystyle {}^{}}$top {\$displaystyle$ T'}의 의미론이 L로 제한되는 T의 의미론인 DTOP $T{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$$displaysty$ T$'}$을$($를) 구축할 수 없다.

이 속성은 결정론적 하향식 트리 오토마타가 상향식 오토마타보다 표현력이 떨어지는 이유와 연결된다. 일단 주어진 경로를 따라 내려가면 다른 경로의 정보에 접근할 수 없다.$변환기$를 코딩하여 변환 f${\displaystyle (x}$, y )${\displaystyle }$→ ${\displaystyle y}${\$displaystyle f(x,$y)\$to$ y$}$; 즉, 입력의 오른쪽 하위 항목을 출력하는 것을 고려하십시오.p가 ID를 인코딩하는 규칙${\displaystyle }q{\displaystyle }$(${\displaystyle f({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$)${\displaystyle }$→ ${\displaystyle p({}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle q(f(x_{1},x_{2})\to p(x_{2})$에 의해 쉽게 수행된다$.$Now let's say we want to restrict this transducer to the finite (and thus, in particular, regular) domain ${\displaystyle \{f(c,a),\ f(c,b)\}}$. We must use the rules ${\displaystyle q(f(x_{1},x_{2}))\to p(x_{2}),\ p(a)\to a,\ p$$(b)\to b$ 그러나 첫 번째 규칙에서 ${\displaystyle {x\mathrm{}}_{}}$ 1 ${\$}은(는) 전혀 나타나지 않는데$$, 왼쪽 아이로부터 아무 것도 생성되지 않기 때문이다.따라서 왼쪽 아이가 c라고 테스트할 수 없다.이와는 대조적으로, 우리는 적절한 아이로부터 생산하기 때문에, 우리는 그것이 a 또는 b라는 것을 테스트할 수 있다.일반적으로 DTOP는 출력을 생성하지 않는 하위 트리의 속성을 테스트할 수 없다는 것이 기준이다.

• DTOP는 구성상 폐쇄되지 않는다.그러나 이 문제는 변환기가 할 수 없는 영역에 대한 시험을 수행할 수 있는 나무 자동화를 변환기에 연결함으로써 해결할 수 있다.^[2]

This follows from the point about domain restriction: composing the DTOP encoding identity on ${\displaystyle \{f(c,a),\ f(c,b)\}}$ with the one encoding ${\displaystyle f(x,y)\to y}$ must yield a transducer with the semantics ${\displaystyle \{$$우리가$알고 $있는$ f$(c,a$)\$mapsto a,\f(c,b$)\mapsto $b\}$는 DTOP에 의해 표현될 수 없다$.$

• 일반 트리 언어의 이미지가 다른 일반 트리 언어에 포함되어 있는지 여부를 테스트하는 형식 검사 문제는 변경할 수 없다.
• 등가성 문제(두 개의 DTOP가 동일한 기능을 정의하는지 여부를 검정)는 분리할 수 있다.^[3]

상향식 트리 변환기(BOT)

나무 오토마타의 단순한 경우처럼, 상향식 나무 변환기는 하향식 변환기와 유사하게 정의되지만, 뿌리부터 잎까지가 아니라 나무의 잎에서 뿌리까지 계속된다.따라서 주요 차이점은 규칙의 $형태$로서 f (${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}{}_{}}$) , …${\displaystyle {}_{}}$,${\displaystyle q_{}}$ ${\displaystyle {}_{}}$) →${\displaystyle {}_{}u}$)${\displaystyle }${\$displaystyle f(q_{1}(x_{1}),\dots ,q_{n}(x_{n})\to q(u$

참조

• Comon, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Löding, Christof; Tison, Sophie; Tommasi, Marc (November 2008). "Chapter 6: Tree Transducers". Tree Automata Techniques and Applications. Retrieved 11 February 2014.
• Hosoya, Haruo (4 November 2010). Foundations of XML Processing: The Tree-Automata Approach. Cambridge University Press. ISBN 978-1-139-49236-2.