Instructor: Bow-Yaw Wang

This lecture covers requisite materials from logic and automata theory. Specific topics include: semantics of classical logic, compactness theorem, completeness theorem, Büchi automata, satisfiability, validity, and QBF.

• Logic: [slides for print] [slides for display]
• Automata: [slides for print] [slides for display] [Supplement]
• Complexity: [slides for print] [slides for display]

• Logic: [Homework #1] [Solutions #1]
• Automata: [Homework #2] [Solutions #2]

• Herbert B. Enderton. A Mathematical Introduction to Logic. Academic Press, 2000.
• John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley.
• Erich Grädel, Wolfgang Thomas, and Thomas Wilke. Automata, Logics, and Infinite Games: A Guide to Current Research. Springer, 2003.