References

The main references for this material is (Sipser 2013). Here is a link to the errata of the book.

The full list of references of books/articles mentioned in this notes are the following. Notice that they include research articles and books that are not necessarily related to the course, but that are mentioned in the notes for completeness.

Cohen, Paul J. 1963. “THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS.” Proceedings of the National Academy of Sciences 50 (6): 1143–48. https://doi.org/10.1073/pnas.50.6.1143.

Cohen, Paul J. 1964. “THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS, II.” Proceedings of the National Academy of Sciences 51 (1): 105–10. https://doi.org/10.1073/pnas.51.1.105.

Gödel, Kurt. 1940. The Consistency of the Continuum Hypothesis. Princeton University Press.

Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation. 3rd edition. Pearson Addison Wesley.

Kozen, Dexter C. 1997. Automata and Computability. Springer New York. https://doi.org/10.1007/978-1-4612-1844-9.

Lee, Lillian. 2002. “Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication.” Journal of the ACM 49 (1): 1–15. https://doi.org/10.1145/505241.505242.

Sipser, Michael. 2013. Introduction to the Theory of Computation. 3rd ed. Cengage Learning.

Valiant, Leslie G. 1975. “General Context-Free Recognition in Less Than Cubic Time.” Journal of Computer and System Sciences 10 (2): 308–15. https://doi.org/10.1016/s0022-0000(75)80046-8.