| Item type |
Trans(1) |
| 公開日 |
2019-05-21 |
| タイトル |
|
|
タイトル |
高階木変換器を経由したマクロ木変換器の直接的融合 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Direct Fusion of Macro Tree Transducers via High-level Tree Transducers |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[発表概要，Unrefereed Presentation Abstract] |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
電気通信大学大学院情報理工学研究科 |
| 著者所属 |
|
|
|
東北大学電気通信研究所 |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Informatics and Engineering, the University of Electro-Communications |
| 著者所属(英) |
|
|
|
en |
|
|
Research Institute of Electrical Communication, Tohoku University |
| 著者名 |
阿部, 和敬
中野, 圭介
|
| 著者名(英) |
Kazuhiro, Abe
Keisuke, Nakano
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
マクロ木変換器（MTT）とは，入出力を木構造とする累積引数付き再帰関数のモデルである．複数のMTTの合成として表現される関数を，1つのMTTで表現することをMTTの融合という．一般にはMTTを融合できるとは限らないが，特定の条件下では融合手法が知られている．VoigtländerとKühnemannは，入力木のコピー回数に関する条件を満たす2つのMTTの融合手法を示した．ただし，1つのMTTで表現できるにもかかわらず，彼らの手法を繰り返すことでは融合できない3つ以上の合成も存在する．Manethは，任意の個数のMTTの合成が最終的な出力木のサイズに関する制約を満たすとき，合成に相当する1つのMTTが構成できることを証明した．しかし，彼の研究は融合可能性の証明が目的のため構成は煩雑である．そこで本発表では，高階木変換器（HTT）を用いてVoigtländerとKühnemannの手法を一般化し，Manethの証明に実用に向いた別証明を与える．HTTとは，MTTの一般化として提案された高階関数のモデルである．本融合は，まずMTTの合成を1つのHTTとして表現し，HTTに現れる高階関数のオーダを下げていくことで，MTTへの融合を実現する．理論上融合が不可能な場合でも，本融合は合成に相当する1つのHTTを得ることができる． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Macro tree transducers (MTTs) are models for recursive functions (with accumulating parameters) on tree-structured data. Constructing a single MTT equivalent to a composition of given MTTs is called ‘fusion’ of the MTTs. Although it is not always possible to fuse given MTTs in general, fusion methods under certain conditions are known. Voigtländer and Kühnemann showed a fusion method of two MTTs restricted about the number of copying an input tree. However, a repetition of their method cannot necessarily fuse more than two MTTs even in the case where there exists a single MTT equivalent to the composition of them. Maneth proved that we can construct an MTT equivalent to a composition of given multiple MTTs restricted about the size of final output trees. However, since he is interested only in the fusibility, the construction is complicated. This presentation gives another proof adapted to practical uses for Maneth's proof as a generalization of Voigtländer and Kühnemann's method with high-level tree transducers (HTTs). Htt was proposed as a generalization of MTT, which is a model of higher-order functions. Our fusion method comprises two steps: first, a single HTT is obtained as a composition of given multiple MTTs; then, the orders of functions are lowered as much as possible. In this approach, we can obtain a ‘fused’ HTT even where there is no single MTT equivalent to the composition of MTTs. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11464814 |
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO）
巻 12,
号 2,
p. 14-14,
発行日 2019-05-21
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7802 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-TPRO1202010.pdf (98.0 kB)
