CIS 262, Fall 2017

Brief description:

The course provides an introduction to the theory of computation. The treatment is mathematical, but the point of view is that of Computer Science. Roughly speaking, the theory of computation consists of three overlapping subareas: (1) formal languages and automata; (2) Models of computation, computability, decidability and undecidability ; (3) complexity theory.

Applications of (1) to programming and language specification and parsing (top-down and bottom-up parsing), and to (2) and (3) to provability in propositional logic will be mentioned, whenever appropriate.


Topics will include: ((*) means: if time permits)

PART I: Languages and Automata

PART II: Models of Computation; Decidability and Undecidability

PART III: Computational Complexity

Back to Gallier Homepage

published by:

Jean Gallier