Introduction to Theory of Computation

Dr. Mitsunori Ogihara joined the University of Miami in 2007 as a Professor in the Department of Computer Science and as the Director of Big Data Analytics & Data Mining in the Center for Computational Science. He serves as the Director of Education and Workforce Development in the Frost Institute for Data Science (he is currently the Director of Master of Science in Data Science and Site co-Director for NSF IUCRC CARTA).Dr. Ogihara obtained his PhD in Information Sciences from the Tokyo Institute of Technology in 1993. From 1994 to 2007, Dr. Ogihara was a Computer Science faculty member at the University of Rochester, where he was promoted to Associate Professor with tenure in 1998, and to Full Professor in 2002. He also served as Chair of the Department from 1999 to 2007.His research interests include data mining, information retrieval, network traffic data analysis, program behavior analysis, molecular computation, and music information retrieval. A prolific scholar, Dr. Ogihara has authored/co-authored four books The Complexity Theory Companion, Music Data Mining, Exploring Data Science with R and the Tidyverse, and for Springer, Fundamentals of Java Programming, and is the author of more than 200 peer-reviewed research papers. Many papers by Dr. Ogihara are through interdisciplinary collaborations. His articles appear in journals and conferences that cover many fields, including psychology, implementation science, library science, chemistry, biology, and digital humanities. He serves as Editor-in-Chief for the Theory of Computing Systems Journal (Springer) and on the editorial board for the International Journal of Foundations of Computer Science (World Scientific).

• Part I Preparation.- Chapter 0 Mathematics and Computer Science Basics.- Part II Formal Language Theory and Automata.- Chapter 1 The Regular Languages.- Chapter 2 Non-Regularity.- Chapter 3 The Context-Free Languages.- Chapter 4 The Pushdown Automaton Model.- Part III Undecidability and Turing Machines.- Chapter 5 The Turing Machines.- Chapter 6 Decidable Languages.- Chapter 7 Undecidable Languages.- Part IV Computational Complexity and Resource-Bounded Turing Machine Computation.- Chapter 8 The Time Complexity.- Chapter 9 The Space Complexity.- Chapter 10 The Theory of NP-Completeness.- Chapter 11 Beyond NP-Completeness.- Part V Advanced Topics in Computational Complexity Theory.- Chapter 12 The Probabilistic Polynomial-Time Classes.- Chapter 13 Circuit Complexity and Unambiguity.