数理論理学セミナーのお知らせ
日時：1月23日(金) 16:00から 場所：東京工業大学 大岡山西８号館 Ｗ棟10階 W1008 話者：鈴木信行（静岡大学） 題目：中間述語論理におけるExistence Propertyに関する話題 --- 小野の問題P52とその周辺 --- 概要： 始めに中間述語論理の簡単な紹介をします。 ざっくり言うと、中間述語論理とは、直観主義述語論理と古典述語論理の「中間」にある述語論理です。 つぎに、existence property と disjunction property と言う性質を考えます。 これらは、直観主義論理の構成性(constructivity)を示す顕著な性質として知られています。 中間述語論理の枠組みでこれらを考察してみると、この2つの性質が独立であることが解ります。 これは、小野の問題P52として知られる問題に否定的解決を与えます。 今回は、これにまつわる若干のことがらも報告したいと思います。
------ 本セミナーは定期的に東工大で開催しているものです。 初めて参加を希望される方はご一報ください。 ----- 鹿島 亮 東京工業大学大学院情報理工学研究科 数理・計算科学専攻 [email protected]
数理論理学セミナーのお知らせ
日時：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]
数理論理学セミナーのお知らせ
日時：11月20日(金) 17:00から 場所：東京工業大学 大岡山西８号館 Ｗ棟10階 W1008 話者：鈴木登志雄（首都大学東京） 題目：非一様な文脈自由言語 概要： 正規言語のクラスは様々な演算について閉じていて扱いやすい。しかし、重要な言語の多くは正規でないため、しばしば閉包性の欠如によって我々をてこずらせる。とくに、文脈自由言語全体のクラスCFLは共通部分をとる操作について閉じていない。二つの文脈自由言語の共通部分として表される集合全体のクラスをCFL(2)で表そう。CFLに比べてCFL(2)がどれぐらい複雑であるかを問うのは、興味深い研究の方向である。Tadaki et al. [2010, Theoret. Comput. Sci.] はCFLの非一様バージョンを導入した。Yamakami [2011, Theoret. Comput. Sci.] は次の問題を提示した。「CFL(2)に属するCFL-immune setで、上記の非一様クラスに属さないものはあるか？」 この講演では、上記問題に対して肯定的な解決を与える (arXiv:1502.00367 [cs.FL]).
------ 本セミナーは定期的に東工大で開催しているものです。 初めて参加を希望される方はご一報ください。 ----- 鹿島 亮 東京工業大学大学院情報理工学研究科 数理・計算科学専攻 [email protected]
数理論理学セミナーのお知らせ
日時：11月24日(火) 10:30から 場所：東京工業大学 大岡山西８号館 Ｗ棟10階 W1008 話者：Zach Weber (University of Otago) 題目：Computation in non-classical foundations? [Joint work with T Meadows] 概要： The Church-Turing Thesis is widely regarded as true, because of evidence that there is only one genuine notion of computation. By contrast, there are nowadays many different formal logics, and different corresponding foundational frameworks. Which ones can deliver a theory of computability? But this apparently straightforward question faces a difficult challenge: mathematical terms are not stable across frameworks. While it is easy to compare what different frameworks say, it is not so easy to compare what they mean. We argue for some minimal conditions that must be met if two frameworks are to be compared.
------ 本セミナーは定期的に東工大で開催しているものです。 初めて参加を希望される方はご一報ください。 ----- 鹿島 亮 東京工業大学大学院情報理工学研究科 数理・計算科学専攻 [email protected]
-
KASHIMA Ryo