コンピュータサイエンス研究会

研究会名：コンピュータサイエンス研究会

開催日：平成21年2月26日（木）13:00～15:00

テーマ：“Typechecking Macro Tree Transducers”

講師：中野圭介（電気通信大学）

開催場所：東北大学　電気情報系3号館 206号室

コンピュータサイエンス研究会講演会の御案内

コンピュータサイエンス研究会
主査小林直樹

下記のようにコンピュータサイエンス研究会の講演会を開催いたしますので，ご案内申し上げます．

日　時：　2009年2月26日(木)13:00～15:00
場　所：　東北大学電気情報系3号館 206号室
題　目：　“Typechecking Macro Tree Transducers”
話　者：　中野圭介（電気通信大学）
概　要：累積変数付き構造的再帰変換の古典的なモデルである Macro Tree Transducer (MTT) は，XML 変換を特徴付ける枠組みとして注目を集めている．特に，正規木言語の逆写像が必ず正規木言語になるという MTT の性質は，XML変換の型検証の基盤となる正規木型推論にも応用されている．しかしながら，複数の MTT の合成に対する型検証の複雑性は nonelementary であることが知られており，一般にこのコストを改善することはできない．本講演では，合成規則や分解規則を適用することにより，それぞれの MTT の性質によっては型検証のコストを改善できることを示す．