This course is a graduate-level introduction to the theory of computation that does not assume prior coursework on the topic. The course catalog says, rather tersely: “A survey of automata theory, formal languages, undecidability and computational complexity.” The description of the associated COS 451 provides more details: Some big questions: What is a computer? How may we model computers and computation? What are the theoretical and practical limits of computation? What do we know about what can, and cannot, and may or may not be computable and efficiently computable? Some more details, from the course catalog: Fundamentals of formal languages and the mathematical theory of computation; finite-state automata, nondeterminism, regular expressions, and Kleenes Theorem; context-free grammars, pushdown automata, the correspondence theorem and the pumping lemma; computability, Turing machines, and the halting problem. Students in COS 550 study the topics in greater depth and breadth than those in COS 451, cover additional readings, and answer additional questions on homeworks, exams, etc. As well, all their work, including that shared with COS 451 is evaluated to a graduate standard.

Prerequisites: COS 301 and COS 250.

Since this is a graduate course, let’s keep the rest of this syllabus brief:

• The entire syllabus of the concurrent COS 451 is included here by reference: http://chaw.eip10.org/cos451/. Please read it. Any contradictions whose resolution is not obvious should be discussed in class.
• There is some flexibility in how a student completes the additional work suggested above. The default is a combination of additional questions on most homeworks and tests, and a few additional readings and submissions. However, there are other viable alternatives, such as a detailed study of a specific topic, summarized by a report and presentation. Please contact me with your ideas within the first week of classes.

News and Reminders:

• Please read the newsgroup for timely announcements.
• Class newsgroup: Local group umaine.cos451 (purposefully shared with COS 451) on NNTP server creak.um.umaine.edu. Web interface to get started: http://chaw.eip10.org/news/.
• The most recent version of this document may be found at http://chaw.eip10.org/cos550/.
• Some sections below point to material in separate documents that are found on the class Web site, linked from the online version of this document.
• Please use the PDF version of this document for printing and reference: cos550.pdf

© 2018 Sudarshan S. Chawathe
Validated HTML 4.01 Transitional. Check.