@misc{oai:uec.repo.nii.ac.jp:00009133,
 author = {高橋, 祐多},
 month = {2019-04-17},
 note = {2018, 構造化されたデータに対する変換は, 関数プログラミングや文書処理において重要な役割を果しており, そのような変換のふるまいのよいクラスを明らかにするため, 様々な計算モデルが提案されている. そのひとつとして, Alur と D'Antoni らによって提案された単一使用制約付き決定性ストリーム木変換器 (STTsur) がある. STTsur はネスト文字列上の変換を定義することができ, ネスト文字列はランク付き木や森といった階層構造を表現することができる. STTsur の単一使用制約は, STTsur が単項二階述語論理による木変換器 (MSOTT) と同等の表現力となるために付けられている制約である. この単一使用制約がないストリーム木変換器の表現力についてはこれまで議論されておらず, その等価性判定が決定可能か否かは未解決問題である. 本論文では STTsur の単一使用制約をなくし, 入力をランク付きの木を表現するネスト文字列, 出力を文字列に制限した決定性ストリーム変換器 (SRTST) を考える. また, SRTST とは別に木を入力とし文字列を出力する変換を扱う計算モデルとして正規先読み付き木から文字列への決定性下降型変換器 (yDTR) がある. yDTR は累積引数を伴わない構造的な再帰関数を扱うことができる. yDTR の等価性判定は決定可能であることが証明されている. 本論文では, SRTST から等価な yDTR , yDTR から等価な SRTST を構成する方法を示すことにより, SRTST と yDTR が同等の表現力を持つことを示す. この証明での SRTST から yDTR への変換は構成的であるため, yDTR の等価性判定を利用することにより, SRTST の等価性判定問題も決定可能となる.},
 title = {ランク付き木から文字列への決定性ストリーム変換器の表現力},
 year = {},
 yomi = {タカハシ, ユウタ}
}