数理論理学セミナーのご案内
日時：10月27日(木)17時から 場所：東京工業大学 大岡山キャンパス 西８号館Ｗ棟 10階 W1008セミナー室 話者：堀畑佳宏（東北大） 題目：弱い算術とconcatenationの理論 概要： 文字列の結合に関する理論（concatenationの理論） TC は、2005年に Grzegorczyk によって導入され、その決 定不可能性が示された。 一方、2009年にはVisser, Svejdar, Ganea がそれぞれ 独立に、TC が Robinson 算術 Q と互いに翻訳 可能であることを示した。 本発表では、concatenation の理論 WTC を新たに導入 し、この理論が Robinson と Tarski によって導入さ れた非常に弱い算術 R と互いに翻訳可能となることを見る。
---------- 会場までの交通案内はこちらから： http://www.titech.ac.jp/about/campus/index.html
----- 鹿島 亮 東京工業大学大学院情報理工学研究科 数理・計算科学専攻 [email protected]
＃＃＃木曜夕方を中心に不定期的にセミナーを開催しています。＃＃＃ ＃＃＃詳細はお問い合わせください。＃＃＃
数理論理学セミナーのご案内
日時：12月1日(木)17時から 場所：東京工業大学 大岡山西８号館W棟11階 W1101セミナー室 話者：江口 直日 （東北大学） 題目： Term-rewriting Characterisations of Computational Complexity Classes -- Towards more natural characterizations 概要： If a computational complexity class (or complexity class for short) is characterised by a set of equations, then one will obtain a term-rewriting characterisation of the complexity class by replacing the defining equations by the corresponding directed equations. The term-rewriting characterisation could be generalised by a reduction order, that is a well-founded monotone algebra over a set of terms, which is compatible with the direction of every defining equation. This talk will discuss about term-rewriting approaches by means of reduction orders towards more natural characterisations of complexity classes, including recent results by the speaker.
This work is partly supported by a grant from John Templeton Foundation (Grant title: Philosophical frontiers in Reverse Mathematics. Project Leaders: Sam Sanders and Keita Yokoyama).
（講演は日本語で行われます） 会場までの交通案内はこちらから： http://www.titech.ac.jp/about/campus/index.html
----- 鹿島 亮 東京工業大学大学院情報理工学研究科 数理・計算科学専攻 [email protected]
＃＃＃木曜夕方を中心に不定期的にセミナーを開催しています＃＃＃ ＃＃＃詳細はお問い合わせください＃＃＃
-
KASHIMA Ryo