|
||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||
4. Descriptive Title: Automata and Complexity Theory | ||||||||||||||||||||||||||||||||||||||||
5. Recommended Abbreviation for Transcript (24 characters including
spaces):
Automata and Complexity |
||||||||||||||||||||||||||||||||||||||||
6. Catalog Description (25 words or less):
Computational machine models and their language classes. Undecidability. Resource-bounded computations. Central complexity-theoretic concepts such as complexity classes, reducibility, and completeness. |
||||||||||||||||||||||||||||||||||||||||
7. Basis: L/G ____X_____ P/F ____X______ Audit ____X______ | ||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||
12. Are you requesting this course satisfy: Humanities ________ Social Science ________ (Must be 1000 or 2000 level) | ||||||||||||||||||||||||||||||||||||||||
13. Probable instructor(s) (Please mark with an asterix any non
tenure-track individuals):
Yan Ding, Richard Lipton, H. Venkateswaran |
||||||||||||||||||||||||||||||||||||||||
15. Required _____________ Elective _____x______ | ||||||||||||||||||||||||||||||||||||||||
16. Please attach a topical outline of the course. |
|
|
Course Outline and Syllabus |
INTRODUCTORY CONCEPTS: Formal languages, operations on languages, and basic properties. REGULAR LANGUAGES: Deterministic and nondeterministic finite automata and their equivalence. Closure properties. Pumping lemma. Myhill-Nerode theorem. CONTEXT-FREE LANGUAGES: Context-free grammars. Ambiguity. Normal forms such as Chomsky Normal Form. Closure properties. Pumping lemms. Pushdown automata. Equivalence of pushdown automata and context-free grammars. Cocke-Kasami-Younger algorithm. Deterministic context-free languages. DECIDABILITY: Turing machines. Recursively-enumerable and recursive languages. Equivalence of varieties of models such as multi-tape and non-deterministic Turing machines with the deterministic Turing machines. Diagonalization. Undecidability of the Halting problem. REDUCIBILITY: Undecidable problems from Language theory. Post Correspondence Problem. Many-one reducibility. COMPLEXITY THEORY: Time complexity. Complexity classes P and NP. Polynomial time reducibility. NP-Completeness. The Cook-Levin theorem. Examples of NP-Complete problems. Space complexity. Savitch's theorem. PSPACE-Completeness. The classes L and NL. NL-Completeness. NL equals CONL. Probabilistic complexity classes. |
Suggested Texts | M. Sipser. Introduction to the theory of Computation, PWS Publishing Company. |