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

研究会名：コンピュータサイエンス研究会　講演会
開催日：2009年10月21日（水） 15:00～17:00
題目：帰納的関数論と項書換の手法を用いた計算量のクラスの分析
講師：江口直日（神戸大学）
開催場所：電気情報系3号館 206号室

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

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

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

日時： 2009年10月21日（水）15:00～17:00
場所：東北大学電気情報系3号館 206号室
題目：帰納的関数論と項書換の手法を用いた計算量のクラスの分析
話者：江口直日（神戸大学）
概要：本講演では非明示的計算量(implicit computational complexity)について講演者の結果を中心にして，歴史的な背景を含めながら説明する．内容は次の2つに大別される．1．S. BellantoniとS. Cook, あるいはD. Leivantらは独立に，tieringやramifyingと呼ばれる方法でP, LINSPACE, PSPACEなどの関数のクラスを表現した．その手法を新井敏康と共に、指数計算量のクラスEXPの関数に拡張した結果を説明する．
2．等式の集まりで定義される関数のクラスを直接分析する代わりに，等式を項の書換規則とみなし(合流性，停止性などの)項書換理論の手法を用いることによって分析する研究がある．この方向性において1の結果に基づいて講演者が得た，EXP関数とPSPACE関数に関する結果を説明する．

1，2の他に，計算量理論と弱い論理体系との関連なども説明する．