学部・大学院区分
Undergraduate / Graduate
情報・博前
時間割コード
Registration Code
2550061
科目区分
Course Category
主専攻科目
科目名 【日本語】
Course Title
オートマトン・形式言語特論
科目名 【英語】
Course Title
Formal Languages and Automata Theory
コースナンバリングコード
Course Numbering Code
GSI156053J
担当教員 【日本語】
Instructor
酒井 正彦 ○
担当教員 【英語】
Instructor
SAKAI Masahiko ○
単位数
Credits
1
開講期・開講時間帯
Term / Day / Period
秋1期 火曜日 3時限
Fall1 Tue 3
対象学年
Year
1年
1
授業形態
Course style

開講系(学部)・開講専攻(大学院)
Subject
情報システム学専攻
必修・選択
Required / Selected


授業の目的 【日本語】
Goals of the Course(JPN)
オートマトン理論は情報科学の土台ともいえ,モデル検査アルゴリズムへの応用など,情報処理全般の理論的基礎となっている。
本講義では,文字列上のオートマトン理論の拡張である木言語上のオートマトン理論とその諸性質を学ぶとともに,オートマトンと論理との関連性を学ぶ。
授業の目的 【英語】
Goals of the Course
Automata and formal language theory is known as the basis of computer science. For its application to compilers and model checking algorithms, it has become the theoretical foundation of all information processing. In this course, we will learn the automaton on tree languages, and discussing its relationship with and application to logic.
到達目標 【日本語】
Objectives of the Course(JPN)
木オートマトン理論を理解すると共に、形式的な定義を理解し、自ら証明を構築できる。
到達目標 【英語】
Objectives of the Course
授業の内容や構成
Course Content / Plan
木オートマトン,木正規表現,木オートマトンによる項上の2項関係や論理との対応などついて議論する。
課題として与えられた証明問題などを解くことを通じて理論的な問題解決能力を涵養する
〔計画〕
1. 木オートマトン
2. 正規木言語の諸性質
3. 木オートマトンと2項関係
4. 弱2階単項論理
5. 木変換
We will learn tree automata, tree regular-expression, difinition of binary relations on terms by tree automata, correspondence between these relations and logic formulae.

1. Tree automata
2. Regular tree languages and their properties
3. Tree antomata and binary relations
4. Weakly second-order monadic logic
5. Tree transfomations
履修条件・関連する科目
Course Prerequisites and Related Courses
離散数学、数理論理学、および、オートマトン理論の知識を有することが望ましい。
成績評価の方法と基準
Course Evaluation Method and Criteria
課外学習のレポート40%,期末試験60%で評価する。2回以上のレポート未提出者,もしくは,期末試験欠席者は「W(欠席)」とする。
教科書・参考書
Textbook/Reference book
授業で用いるスライドのハンドアウトをWEB上に用意する。
参考書:Hubert Comon, et.al, Tree Automata Techniques and Applications, http://tata.gforge.inria.fr/
課外学習等(授業時間外学習の指示)
Study Load(Self-directed Learning Outside Course Hours)
講義において説明した理論を理解し,活用できるようにするために課題を与える。
授業開講形態等
Lecture format, etc.
原則対面にて実施する。詳細はnuct講義ページを通じて通知する。
遠隔授業(オンデマンド型)で行う場合の追加措置
Additional measures for remote class (on-demand class)