論文誌(トランザクション)
論文誌(トランザクション)
 |
|
| ■文献番号： | IPSJ-TPRO0204005 |
■文 献 名 ： |
Computing the Cost of Typechecking of Composition of Macro Tree Transducers |
| ■著 者： |
Keisuke Nakano (The University of Electro-Communications)
|
| ■言 語 ： | 英語 |
| ■発行年月日： |
2009年 8月 28日
Vol.2 No.4 |
| ■ページ数： | 11ページ 本誌掲載頁：53-63ページ |
| ■サ イ ズ ： | A4 |
■価 格： |
\735
※ ペーパー(論文単位)の価格です。 PDF(ダウンロード)の価格はこちら |
| ■抄 録： | Macro tree transducers are a classical formal model for structural-recursive tree transformation with accumulative parameters. They have recently been applied to model XML transformations and queries. Typechecking a tree transformation means checking whether all valid input trees are transformed into valid output trees, for the given regular tree languages of input and output trees. Typechecking macro tree transducers is generally based on inverse type inference, because of the advantageous property that inverse transformations effectively preserve regular tree languages. It is known that the time complexity of typechecking an n-fold composition of macro tree transducers is nonelementary. The cost of typechecking can be reduced if transducers in the composition have special properties, such as being deterministic or total, or having no accumulative parameters. In this paper, the impact of such properties on the cost of typechecking is investigated. Reductions in cost are achieved by applying composition and decomposition constructions to tree transducers. Even though these constructions are well-known, they have not yet been analyzed with respect to the precise sizes of the transducers involved. The results can directly be applied to typechecking XML transformations, because type formalisms for XML are captured by regular tree languages. |
| ■カテゴリ： |
論文誌(トランザクション)
論文誌 プログラミング（PRO）
通常論文 |
