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

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

開催日：平成20年10月15日（水）15:00～17:00

テーマ：Macro Tree Transducers and Their Complexity

講師：稲葉一浩（東京大学）

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

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

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

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

日時：2008年10月15日（水）15:00～17:00
場所：東北大学電気情報系3号館 201号室
題目：Macro Tree Transducers and Their Complexity
話者：稲葉一浩（東京大学）
概要：近年、XML変換プログラミング言語など木構造変換のモデルとして脚光を浴びているMacro Tree Transducer (MTT) について紹介する。特に、演者の最近の研究テーマである、MTT に関する種々の決定問題の計算量に関して – 複数の MTT の合成で表現された木変換プログラムから、余計な中間データを全く生成しない形式 “Garbage-free form” への静的な変形- 木構造を、単一の木を生成する文脈自由文法で表現することによる空間計算量の圧縮などの技法を解説する。