Error: no such theme PatternSkinTheme

CSC 341: Automata, Formal Languages, and Computational Complexity

Overview

CSC 341 deals in a formal and mathematically rigorous way with the nature of computation, determining which kinds of problems computational devices of various designs can solve and the resources they use in solving various kinds of problems. We consider several abstract models of computation (finite-state automata, regular expressions, context-free grammars, pushdown automata, Turing machines, etc.) and develop and use several characteristic proof techniques (construction, problem reduction or transformation, diagonalization, etc.).

Goals

We expect the students who take this course

  • to develop an exact understanding of the powers and limitations of the kinds of automata that we discuss;
  • to acquire facility in applying the proof techniques that we study and in recognizing cases in which it is appropriate to use them;
  • more generally, to distinguish rigorous mathematical argumentation from casual presentation of a line of reasoning, and to write clearly and accurately in either mode;
  • to recognize commonly encountered problems that are either insoluble or intractable and to be able to demonstrate their insolubility or intractability.

Objectives

As criteria of success in meeting these goals, we set as course objectives
  • the ability to determine whether certain formal languages are regular, context-free, or recursively enumerable, by applying relevant lemmas and theorems developed in the course, and to prove that one's determinations are correct;
  • the ability to propose automata that accept certain formal languages, or grammars that generate them;
  • the ability to transform and combine automata in certain specified ways, adapting them to the solution of different (but equally well-defined) problems;
  • the ability to prove the equivalence of certain models of computation, by systematically correlating elements of the models and demonstrating that each step in a computation carried out under one model can be emulated by the other;
  • the knowledge of certain properties of models of computation, specifically:
    • the existence and construction of a universal Turing machine;
    • the undecidability of the halting problem for Turing machines, and of certain problems that are reducible to that problem;
    • the existence and construction of a Turing machine that prints out its own description, and of certain related machines that use their own descriptions for computational purposes;
    • the uncomputability of minimal descriptions of Turing machines; and
    • the undecidability of the arithmetic of natural numbers under addition and multiplication;
  • the knowledge of the nature and composition of some complexity classes of problems, including P and NP; and
  • the knowledge of the existence and structure of several NP-complete problems, including 3SAT (the satisfiability or unsatisfiability of Boolean formulas in conjunctive normal form having exactly three literals in each clause).

Potential Topics

Topics that are regularly dealt with in CSC 341 include:
  • mathematical induction, including course-of-values induction
  • deterministic and nondeterministic finite automata;
  • regular expressions and regular languages;
  • context-free grammars;
  • pushdown automata;
  • deterministic and nondeterministic Turing machines;
  • multitape Turing machines and other variations in Turing-machine design;
  • cardinalities of infinite sets;
  • diagonalization arguments;
  • decidability;
  • Turing reducibility;
  • mapping reducibilty;
  • the recursion theorem;
  • the parameter theorem;
  • definitions of computational complexity;
  • the P and NP complexity classes;
  • NP-completeness; and
  • the Cook-Levin theorem.
Topics that are often dealt with in CSC 341 include:
  • semi-Thue production systems;
  • the Post correspondence problem;
  • recursive function theory;
  • oracle machines;
  • information and compressibility;
  • the PSPACE complexity class;
  • PSPACE-completeness;
  • the L and NL complexity classes;
  • approximation algorithms;
  • probabilistic algorithms; and
  • cryptography.
Topic revision: r4 - 2011-02-02, JohnDavidStone
 

This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Foswiki? Send feedback