ツリートランスデューサー

理論計算機科学および形式言語理論において、ツリー トランスデューサ(TT) は、ツリーを入力として受け取り、出力 (通常は他のツリーですが、単語や他の構造を生成するモデルも存在します) を生成する抽象マシンです。大まかに言えば、単語トランスデューサが単語オートマトンを拡張するのと同じように、ツリー トランスデューサはツリーオートマトンを拡張します。

単語の代わりにツリー構造を操作することで、TT は形式言語または自然言語の構文指向変換をモデル化できます。ただし、TT は、アルゴリズムの複雑さ、閉包特性などの点で、単語の対応物ほど適切に動作しません。特に、主要なクラスのほとんどは、合成に関して閉じていません。

ツリートランスデューサーの主なクラスは次のとおりです。

TOP T は、次の条件を満たすタプル( Q、Σ、Γ、I、δ )です。

• Q は有限集合、つまり状態の集合です。
• Σ は有限のランク付けされたアルファベットであり、入力アルファベットと呼ばれます。
• Γ は有限のランク付けされたアルファベットであり、出力アルファベットと呼ばれます。
• I は初期状態の集合であるQのサブセットであり、
• δ はという形式の規則 の集合であり、ここでfは Σ の記号、nはfの引数、qは状態、uは Γ および 上の木であり、このようなペアはヌル引数である。${\displaystyle q(f(x_{1},\dots ,x_{n}))\to u}$${\displaystyle Q\times 1..n}$

例えば、

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

は規則である（通常はペアではなく）と書く。その直感的な意味は、 qの作用により、ルートに f 、3つの子を持つ木が次のように変換されるということである。${\displaystyle q(x_{i})}$${\displaystyle (q,x_{i})}$

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

ここで、再帰的に、およびは、それぞれ最初の子への の適用と、 3 番目の子への の適用に置き換えられます。 ${\displaystyle q'(x_{1})}$${\displaystyle q''(x_{3})}$${\displaystyle q'}$${\displaystyle q''}$

トランスデューサTの各状態とT自体のセマンティクスは、入力ツリー (Σ 上) と出力ツリー (Γ 上) 間の バイナリ関係です。

意味論を形式的に定義する方法は、右辺の呼び出しが の形式で書かれ、状態qが単項記号である限り、を項書き換えシステムとして見ることである。この場合、状態qの意味論は次のように与えられる。 ${\displaystyle \delta}$${\displaystyle q(x_{i})}$${\displaystyle [\![q]\!]}$

${\displaystyle [\![q]\!]=\{u\mapsto v\mid u{\text{ は }}\Sigma 上の木、\ v{\text{ は }}\Gamma {\text{ 上の木、}}q(u)\to _{\delta }^{*}v\} です。}$

Tのセマンティクスは、その初期状態のセマンティクスの和集合として定義されます。

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

ツリーオートマトンと同様に、TOP は、 δ の 2 つのルールが同じ左側を共有せず、初期状態が最大で 1 つしかない場合、決定論的( DTOPと略記) であると言われます。その場合、DTOP のセマンティクスは、入力ツリー (Σ 上) から出力ツリー (Γ 上) への部分関数であり、DTOP の各状態のセマンティクスも同様です。

トランスデューサのドメインは、そのセマンティクスのドメインです。同様に、トランスデューサのイメージは、そのセマンティクスのイメージです。

• DTOP はunionの下で閉じられていません。これは、決定論的単語トランスデューサーの場合にすでに当てはまります。
• DTOPのドメインは正規木言語である。さらに、そのドメインは、初期DTOPのサイズの最大指数関数の大きさの決定論的トップダウン木オートマトン（DTTA）によって認識可能である。^[1]

ドメインが DTTA で認識可能であることは、DTOP 規則の左側が DTTA の場合と同じであることを考えると、驚くことではありません。最悪の場合の指数関数的爆発の理由 (単語の場合では存在しない) については、規則 について考えてみましょう。計算が成功するためには、両方の子について計算が成功する必要があります。つまり、右の子は のドメイン内にある必要があります。左の子については、と の両方のドメイン内にある必要があります。一般に、サブツリーはコピーできるため、決定論にもかかわらず、DTTA とは異なり、実行中に 1 つのサブツリーを複数の状態で評価できます。したがって、DTOP のドメインを認識する DTTA の構築では、状態のセットを考慮し、それらのドメインの交差を計算する必要があり、これが指数関数です。線形DTOP の特殊なケース、つまり各 が各規則の右側に最大で 1 回出現する DTOP では、構築は時間と空間において線形です。${\displaystyle q(f(x_{1},x_{2}))\to g(p_{1}(x_{1}),p_{2}(x_{1}),p_{3}(x_{2}))}$${\displaystyle p_{3}}$ ${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle x_{i}}$

• DTOP のイメージは通常のツリー言語ではありません。

変換 をコード化するトランスデューサー、つまり入力の子を複製するトランスデューサーを考えてみましょう。これは、p が恒等式をコード化する規則 によって簡単に実行できます。入力の最初の子に制約がない場合、画像は古典的な非正規ツリー言語です。${\displaystyle f(x)\to g(x,x)}$${\displaystyle q(f(x_{1}))\to g(p(x_{1}),p(x_{1}))}$

• しかし、 DTOP のドメインは通常のツリー言語に制限することはできません。つまり、 DTOP Tと言語Lが与えられた場合、の意味がLに制限されたTの意味になるようなDTOP を一般に構築することはできません。${\displaystyle T'}$${\displaystyle T'}$

この特性は、決定論的トップダウン木オートマトンがボトムアップオートマトンよりも表現力に乏しい理由に関係しています。つまり、特定のパスに進むと、他のパスからの情報にはアクセスできなくなります。変換 をコーディングするトランスデューサ、つまり入力の右の子を出力するトランスデューサを考えてみましょう。これは、p が恒等式をエンコードする規則 によって簡単に実行できます。ここで、このトランスデューサを有限（したがって、特に通常の）ドメイン に制限するとします。規則 を使用する必要があります。ただし、最初の規則では、左の子からは何も生成されないため、 はまったく表示されません。したがって、左の子がcであることをテストすることはできません。対照的に、右の子から生成するため、それがaまたはbであることをテストできます。一般に、基準は、 DTOP は出力を生成しないサブツリーの特性をテストできないということです。${\displaystyle f(x,y)\to y}$${\displaystyle q(f(x_{1},x_{2}))\to p(x_{2})}$${\displaystyle \{f(c,a),\ f(c,b)\}}$${\displaystyle q(f(x_{1},x_{2}))\to p(x_{2}),\ p(a)\to a,\ p(b)\to b}$${\displaystyle x_{1}}$

• DTOPは合成に関して閉じていない。しかし、この問題は先読みを追加することで解決できる。先読みとは、トランスデューサに結合されたツリーオートマトンで、トランスデューサが実行できないドメインのテストを実行できる。 ^[2]

これは、ドメイン制限に関する点から導かれます。つまり、 上の DTOP エンコーディング ID を1 つのエンコーディングと合成すると、セマンティクス を持つトランスデューサが生成されますが、これは DTOP では表現できないことが分かっています。${\displaystyle \{f(c,a),\ f(c,b)\}}$${\displaystyle f(x,y)\to y}$${\displaystyle \{f(c,a)\mapsto a,\ f(c,b)\mapsto b\}}$

• 型チェック問題 (正規木言語のイメージが別の正規木言語に含まれているかどうかをテストする) は決定可能です。
• 同値性問題（2つのDTOPが同じ関数を定義しているかどうかをテストする）は決定可能である。^[3]

より単純なツリーオートマトンの場合と同様に、ボトムアップ ツリー トランスデューサはトップダウン ツリー トランスデューサと同様に定義されますが、ルートからリーフではなく、ツリーのリーフからルートに進みます。したがって、主な違いはルールの形式にあり、次の形式になります。 ${\displaystyle f(q_{1}(x_{1}),\dots ,q_{n}(x_{n}))\to q(u)}$

• コモン、ヒューバート。マックス・ドーシェ。ギルロン、レミ。ジャックマール、フィレンツェ;ルギエズ、デニス。レーディング、クリストフ。ティソン、ソフィー。マーク・トンマシ（2008年11月）。 「第 6 章: ツリートランスデューサー」。ツリー オートマトンの技術と応用。2014 年2 月 11 日に取得。
• 細谷晴夫（2010年11月4日）。XML処理の基礎：ツリーオートマトンアプローチ。ケンブリッジ大学出版局。ISBN 978-1-139-49236-2。