[logic-ml] セミナー案内

[KASHIMA Ryo]

数理論理学セミナーのお知らせ

日時：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]).

------
本セミナーは定期的に東工大で開催しているものです。
初めて参加を希望される方はご一報ください。
-----
鹿島 亮
東京工業大学大学院情報理工学研究科
数理・計算科学専攻
kashima at is.titech.ac.jp