著者

阿部 和敬 中野 圭介

雑誌

情報処理学会論文誌プログラミング(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を得ることができる.