数理論理学セミナーのお知らせ
日時：10月30日(金) 15:10から 場所：東京工業大学 大岡山西８号館 Ｗ棟10階 W1008
【１】 話者：新屋良磨（東工大・博士課程） 題目：正規言語の零壱則 概要： 「論理Lが零壱則を持つ(L has the 0-1 law)」とは，おおまかに言うとLで記述できる命題が 「ほとんど真(almost surely true)」か「ほとんど偽(almost surely false)」の2種類しかないことを言う． 本発表では，全順序と単項述語を語彙に持つ「文字列上の論理」における零壱則について，正規言語の variety theoryの技法を用いた代数的・オートマトン的な特徴付けの証明を解説する． また，零壱則の特徴付けから導かれるいくつかの性質について考察し，正規言語より表現力の高い言語 クラスへの拡張についても言及する． 参考文献：本発表の内容は次の論文に従うものである． "An Automata Theoretic Approach to the Zero-One Law for Regular Languages: Algorithmic and Logical Aspects" http://arxiv.org/abs/1509.07209 論理・オートマトンの基礎は仮定する．言語・代数・論理の繋がりやvariety theoryの初歩を解説した以下の 資料にちらっと目を通しておくことを薦める． 「正規言語と代数と論理の対応：An Introduction to Eilenberg’s Variety Theorem」 http://www.slideshare.net/sinya8282/an-introduction-to-eilenbergs-variety-th...
【２】 話者：沖坂祥平（東北大・博士課程） 題目：Lindstrom拡大の定義可能性について 概要： 有限モデル理論において一階述語論理の表現力は非常に乏しいことが知られている。 一階述語論理を拡張する1つの手法として有限モデルのクラスKに対応するLindstrom quantifierを新たに加えることが考えられるが本発表ではクラスKの性質が、対応する量化記号を加えた論理の表現力にどの程度影響するかを考察する。
------ 本セミナーは定期的に東工大で開催しているものです。 初めて参加を希望される方はご一報ください。 ----- 鹿島 亮 東京工業大学大学院情報理工学研究科 数理・計算科学専攻 [email protected]