Login

• CS SFU
• > Portal
• > Outlines

Computing Science Course Outlines

Course Outline - CMPT 981 - Spec. Top. Theoretical Cmpt

Information

Calendar Objective/Description

Spec. Top. Theoretical Cmpt

Instructor's Objectives

This course introduces students to the connections between computational complexity and automata theory on one hand, and mathematical logic on the other. Part 1 will focus on Descriptive Complexity, and Part 2 on Logic and Automata. Course Objectives: The goal of the course is to equip students with tools and techniques to address problems in theoretical computer science. They will be exposed to some of the major open problems of Descriptive Complexity, and current efforts to solve them. By the end of the course, students will learn different fragments of logics, connections between computational complexity and expressiveness of a logic, and connections between logic and automata theory. In particular, they will see how some major complexity classes (such as P and NP) can be characterized in logic. A special emphasis will be put on logics for which expressiveness separation results have been established. One of such logics will be discussed extensively, and its connections with automata will be explained in detail.

Prerequisites

see go.sfu.ca

Topics

• first-order logic, second-order logic monadic second-order logic (MSO),
• finite model theory and descriptive complexity,
• Fagin's theorem (characterizing NP on arbitrary structures),
• characterizing P and lower complexity classes on ordered structures,
• transitive closure logic (TC) and deterministic transitive closure logic (DTC),
• separation of TC and DTC on arbitrary structures,
• monadic NP and separation of existential and universal fragments of MSO,
• automata on finite strings and trees,
• regular expressions and expressing imperative programming constructs,
• connections between regular languages, MSO and linear dynamic logic,
• satisfiability and validity of MSO on strings.

Grading

Will be discussed in the first week of classes.

Academic Honesty Statement

Academic honesty plays a key role in our efforts to maintain a high standard of academic excellence and integrity. Students are advised that ALL acts of intellectual dishonesty will be handled in accordance with the SFU Academic Honesty and Student Conduct Policies ( http://www.sfu.ca/policies/gazette/student.html ).