• 検索結果がありません。

拡張線形ボトムアップ木変換器の関数性の多項式時間判定

N/A
N/A
Protected

Academic year: 2021

シェア "拡張線形ボトムアップ木変換器の関数性の多項式時間判定"

Copied!
1
0
0

読み込み中.... (全文を見る)

全文

(1)情報処理学会論文誌. プログラミング. Vol.8 No.4 15 (Dec. 2015). 発表概要. 拡張線形ボトムアップ木変換器の関数性の多項式時間判定 石原 鷹1,a). 橋本 健二1. 関 浩之1. 酒井 正彦1. 2015年6月4日発表. 木変換器は XML 文書変換やコンパイラなどにおける構文主導型変換のモデルとして用いられる.木変 換器に関する基本的な判定問題の 1 つとして関数性の判定があげられる.関数性判定は木変換器の等価性 や可逆性などの解析において有用である.木変換器のクラスの 1 つであるボトムアップ木変換器について は,関数性は多項式時間で決定可能であることが Seidl により示されている.しかし,ボトムアップ木変 換器より真に表現能力の高い木変換器のクラスとして Engelfriet らにより提案された拡張ボトムアップ木 変換器に対しては,関数性が多項式時間で決定可能であるかはまだ知られていない.本研究では,拡張ボ トムアップ木変換器の関数性が多項式時間で決定可能であるかを明らかにするべく,Seidl の手法に対して 拡張を試みた.従来の Seidl の手法では,ボトムアップ木変換器から,2 つの出力関数を備えたペアリング という変換器を構成し,ペアリングの依存グラフを用いることでその出力等価性を判定する.しかし,入 力が拡張線形ボトムアップ木変換器の場合にペアリングを構成しようとすると,単一の木でない部分出力 を生成する規則が必要となるが,従来のペアリングのクラスではそのような規則を許していない.そこで, そのような規則を許すようにペアリングのクラスと構成方法の拡張を行った.次いで,そのペアリングの クラスに対応するように出力等価性の判定条件を拡張した.これらにより,拡張線形ボトムアップ木変換 器の関数性が多項式時間で決定できることを示した.. Deciding Functionality of Linear Extended Bottom-up Tree Transducers in Polynomial Time Taka Ishihara1,a). Kenji Hashimoto1. Hiroyuki Seki1. Masahiko Sakai1. Presented: June 4, 2015. Tree transducers are used as formal models of XML document transformations and syntax-directed translations. One of basic decision problems of tree transducers is the functionality problem, which is useful for deciding equivalence and invertibility of transducers. As a complexity result of the functionality problem, it was shown by Seidl that functionality of bottom-up tree transducers is decidable in polynomial time. However, for extended bottom-up tree transducers, which were proposed by Engelfriet et. al., it is still open whether functionality is decidable in polynomial time even for its linear subclass. We extend the polynomial decision algorithm for ordinary bottom-up tree transducers to extended linear bottom-up tree transducers. In the algorithm for ordinary bottom-up tree transducers, a transducer with two output functions, called the pairing, is constructed, and then equivalence of the two output functions of the pairing is checked by using its trace graph. We extend the class of pairings for extended linear bottom-up tree transducers. Then, we give an extended sufficient and necessary condition of equivalence of the two output functions with respect to the trace graph of the extended pairing. We show that functionality of linear extended bottom-up tree transducers can be decided in polynomial time.. 1 a). 名古屋大学大学院情報科学研究科 Graduate School of Information Science, Nagoya University [email protected]. c 2015 Information Processing Society of Japan . 15.

(2)

参照

関連したドキュメント

From here they obtained a combinatorial in- terpretation for the Kronecker coefficients when λ is a product of homogeneous symmetric functions, and µ and ν are arbitrary skew

2 Combining the lemma 5.4 with the main theorem of [SW1], we immediately obtain the following corollary.. Corollary 5.5 Let l > 3 be

Using notions from Arakelov theory of arithmetic curves, van der Geer and Schoof were led to introduce an analogous zeta function for number fields [GS].. In [LR] Lagarias and

It is suggested by our method that most of the quadratic algebras for all St¨ ackel equivalence classes of 3D second order quantum superintegrable systems on conformally flat

The dimension d will allow us in the next sections to consider two different solutions of an ordinary differential equation as a function on R 2 with a combined expansion.. The

Kilbas; Conditions of the existence of a classical solution of a Cauchy type problem for the diffusion equation with the Riemann-Liouville partial derivative, Differential Equations,

We present sufficient conditions for the existence of solutions to Neu- mann and periodic boundary-value problems for some class of quasilinear ordinary differential equations.. We

The author, with the aid of an equivalent integral equation, proved the existence and uniqueness of the classical solution for a mixed problem with an integral condition for