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

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

研究会名:コンピュータサイエンス研究会 講演会
開催日: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の他に,計算量理論と弱い論理体系との関連なども説明する.

問い合わせ先

小林  直樹
kobaecei.tohoku.ac.jp