[logic-ml] セミナー案内

[KASHIMA Ryo]

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

日時：12月20日(水) 16:50から
場所：東京工業大学 大岡山西８号館 Ｗ棟10階 W1008
話者：新屋良磨（秋田大）
題目：統語的曖昧性・普遍性判定問題の決定可能性
概要：
統語的曖昧性とは種々の形式文法において「文法が曖昧かどうか」を表す性質であり，
自然言語の形式化やプログラミング言語の構文設計においても重要となる性質である．
本講演では
①形式言語理論の思想や基礎から始め，
②文脈自由文法の統語的曖昧性の定義といくつかの基本的な性質(曖昧/無曖昧性と超越関数/代数関数とのつながり)を説明し，
③曖昧/無曖昧な文脈自由文法における普遍性判定問題(任意の文字列を導出するかどうかの判定)が決定不能/決定可能であることを解説する．
特に，③の決定可能側の議論はTarskiの量化子除去を用いる興味深いものとなっている．
以上は全て古典的な結果であり話者の貢献は何もないが，時間があれば話者の最近の統語的曖昧性に関する研究についても軽く紹介したい．

本講演は、数学基礎論若手の会での話者の発表内容に、さらに③の証明についての解説を付加したものである。

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