Core concepts like decidability, undecidability, and NP-completeness, to advanced topics like randomized complexity are featured in this book by IDSC Director of Workforce Development and Education, Dr. Mitsunori Ogihara. The book is a comprehensive introduction to the theory of computation for students in computer science and related disciplines, and includes end-of-chapter exercises, an appendix of major results, and a solutions manual for instructors.
About the Book
This textbook aims to provide a comprehensive introduction to the theory of computation for upper-level undergraduate students and first-year graduate students in computer science and related disciplines. It covers a wide range of foundational topics essential for understanding the principles and applications of computation.
The book begins with regular languages, exploring finite automata, nondeterministic finite automata, regular expressions, and the equivalence among these apparatuses. It explores state minimization and the Myhill-Nerode Theorem, offering techniques such as pumping lemmas to identify non-regular languages and using the Myhill-Nerode Theorem for non-regularity proofs. Additionally, the closure properties of regular languages are examined.
Context-free languages are another focal point, where the text discusses context-free grammars, Chomsky normal form (CNF) grammars, pushdown automata (PDA), and their equivalences. The book includes pumping lemmas and closure properties using CNF grammars and PDA analysis, as well as identifying non-context-free languages and understanding leftmost derivations.
Turing machine models are thoroughly covered, with various models and simulations explained. The book outlines configurations, the Church-Turing Thesis, and differentiates between recursive and recursively enumerable languages.
Decidability and undecidability are critical topics in the text, addressing decidable problems, diagonalization, the halting problem, and Rice’s Theorem. It also provides a characterization of decidability, discusses the Post Correspondence Problem, and examines the lower levels of the arithmetical hierarchy.
The textbook also delves into computational complexity classes, defining time and space complexity classes, and presenting efficient simulations and hierarchy theorems, including the Hennie-Stearns Theorem. It includes examples of problems in P and NP, providing a clear understanding of these classifications.
NP-completeness is explored in detail, covering SAT and 3SAT, canonical complete problems, and various NP-complete problems. The book extends to space complexity classes, discussing PSPACE complete problems, NL-complete problems, and proving that NL=coNL.
Finally, the text ventures beyond NP-completeness, discussing Ladner’s construction of non-NPC sets, randomized complexity classes, and concepts such as BPP and the polynomial hierarchy. It also examines polynomial size circuits, providing a comprehensive view of the landscape of computational complexity. Buy Now
About the Author
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 Frost Institute for Data Science and Computing (IDSC) (then named the Center for Computational Science). He currently serves as the Director of Education and Workforce Development at IDSC, as the Director of the UM Master of Science in Data Science program, and as Site co-Director for NSF University of Miami CARTA, an Industry/University Cooperative Research Center (IUCRC) dedicated to advancing “faster-than-life” data analytics.
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 Department Chair 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 five books The Complexity Theory Companion (2001), Music Data Mining (2011), Exploring Data Science with R and the Tidyverse (2023), Fundamentals of Java Programming (2018), and in Japanese 複雑さの階層 (Heirarchy of Complexity), and he 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.
Dr. Ogihara also serves as Editor-in-Chief for the Theory of Computing Systems Journal (Springer) and is on the editorial board for the International Journal of Foundations of Computer Science (World Scientific).
