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

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

単語ではなく木構造を操作することで、TTは形式言語や自然言語の構文指向変換をモデル化できます。しかし、TTはアルゴリズムの複雑さ、閉包性などの観点から、単語ベースのものほど振る舞いがよく​​ありません。特に、主要なクラスのほとんどは合成に関して閉じていません。

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

トップダウンツリートランスデューサー（TOP）

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の特性

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

DTOP 規則の左側が DTTA の場合と同じであることを考えると、ドメインが DTTA で認識可能であることは驚くべきことではありません。最悪のケースで指数関数的に爆発する理由 (ワードの場合は存在しない) については、規則 について考えてみましょう。計算が成功するためには、両方の子について計算が成功する必要があります。つまり、右の子は のドメイン内にある必要があります。左の子については、と の両方のドメイン内にある必要があります。一般に、サブツリーはコピーできるので、決定論的であるにもかかわらず、また DTTA とは異なり、実行中に単一のサブツリーを複数の状態で評価できます。したがって、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が与えられた場合、その意味がTの意味と同じでLに限定されるような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]

ボトムアップツリートランスデューサー（BOT）

より単純な木オートマトンの場合と同様に、ボトムアップ型の木トランスデューサはトップダウン型の木トランスデューサと同様に定義されますが、木の根から葉へではなく、葉から根へと進みます。したがって、主な違いは規則の形式にあり、規則は という形式になります。 ${\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。

1. ベイカー、BS：トップダウンとボトムアップのツリー伝達の構成。情報制御41(2)、186-213（1979）
2. Maneth, Sebastian (2015年12月). 「ツリートランスデューサにおける決定可能同値性問題に関する概説」(PDF) . International Journal of Foundations of Computer Science . 26 (8): 1069– 1100. doi :10.1142/S0129054115400134. hdl : 20.500.11820/2f1acef4-1b06-485f-bfd1-88636c9e2fe6 .
3. 「ツリートランスデューサIに関する決定可能性の結果」www.inf.u-szeged.hu。