著者

阿部 和敬 中野 圭介

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.12, no.2, pp.14, 2019-05-21

---

マクロ木変換器(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を得ることができる.

著者

阿部 和敬 中野 圭介

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.12, no.2, pp.14, 2019-05-21

---

マクロ木変換器(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を得ることができる.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.