木から文字列への決定性降下型変換器の早期化

高橋, 祐多, 中野, 圭介

木から文字列への決定性降下型変換器（deterministic top-down tree-to-string transducers，yDTs）は，木構造データを入力とし，文字列を出力するような関数を扱うモデルの1つである．与えられた2つのyDTが，あらゆる同じ入力に対して同じ出力をするかという等価性判定は，決定可能であることが知られている．既存の等価性判定アルゴリズムは，2つの半アルゴリズムを組み合わせることで等価性判定を行っているため，計算量の見積りが不可能である．一方，yDTが線型の場合，正規形を求めることでたかだか指数時間で決定できることが知られている．そのアルゴリズムでは，言語の最大共通接頭辞・接尾辞や周期性を利用することで早期化を行った後，最小化することで正規形を求め，等価性判定を行っている．そこで，計算量を見積もることができるyDTの等価性判定アルゴリズムの実現に向け，本発表では線型yDTの等価性判定アルゴリズムにおいて用いられる早期化を非線型yDTに対して適用できるよう一般化する．具体的には，yDTに対して正規先読みを追加することで，早期に出力可能な文字列を可能な限り早く出力する正規先読み付きyDTを構築する．

A deterministic top-down tree-to-string transducer (yDT) is a model of functions which transform tree-structured data to a string. It is known that the equivalence problem on yDTs is decidable, that is, we can effectively check if given two yDTs output the same string for every input. Since the existing algorithm for the equivalence problem consists of two semi-algorithms, it is impossible to estimate its computational complexity. In the case where given yDTs are linear, the equivalence can be decided in at most exponential time to the size of yDT through their ‘normal forms’ which is obtained by constructing earliest yDT and minimizing the size of it. This approach relies on properties of the longest common prefix/suffix and the periodicity of language, which has never been discussed for general yDTs. In this presentation, we study earliest yDTs as the first step of another algorithm of which computational complexity can be determined. We introduce regular-lookahead to yDTs for generalizing the construction of earliest linear yDT. It makes it possible that the rule of yDT yields string as possible as earlier.

木から文字列への決定性降下型変換器の早期化

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

詳細情報詳細情報について

書き出し

問題の指摘

木から文字列への決定性降下型変換器の早期化

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

詳細情報 詳細情報について

書き出し

問題の指摘

参加プロジェクトリスト

詳細情報詳細情報について