Sendai Logic Mathematical Institute, Tohoku University, Sendai, Miyagi, Japan

2018.06.08. 中林 美郷

Rabinの定理と無限木オートマトン

  • Date/Time: June 8, 2018 (Friday) / 16:00 - 17:00

  • Speaker: 中林 美郷 氏 (東北大学大学院 理学研究科)

  • Venue: Rm 1201, Science Complex A, Tohoku Univ.

  • Abstract: Rabinの定理とは,無限二分木のMonadic second-order theoryがdecidableであることを主張する定理である.本発表ではオートマトンの基本事項について述べながら,Rabinの定理の証明を行う.