The Pillars of Computation Theory

From the reviews: Rosenberg (Colorado State) charts another path by teaching the major themes that underlie all of computer science. He identifies three themes, or pillars: state, encoding, and nondeterminism. This work is helpful for mathematically prepared undergraduates . Summing Up: Recommended. Upper-division undergraduates, graduate students, researchers, and faculty. (P. Cull, Choice, Vol. 47 (9), May, 2010) The authors intentions are clear from the very beginning: he wants to change the way computation theory is taught to undergraduates. The intended audience includes advanced undergraduates and beginning graduate students. student whose interests run to theoretical computer science, this would be a challenging and attractive book. For more typical students there are no exercises directly tied to the immediate text and few anywhere that are more routine the kind of many students need to ground themselves in the subject. (William J. Satzer, The Mathematical Association of America, March, 2010) This authoritative, tightly woven book is unsurpassed as the definitive computation theory text and reference it has my highest recommendation. (George Hacken, ACM Computing Reviews, August, 2010)

PROLEGOMENA.- Mathematical Preliminaries.- STATE.- Online Automata: Exemplars of #x201C;State#x201D;.- Finite Automata and Regular Languages.- Applications of the Myhill#x2013;Nerode Theorem.- Enrichment Topics.- ENCODING.- Countability and Uncountability: The Precursors of #x201C;Encoding#x201D;.- Enrichment Topic: #x201C;Efficient#x201D; Pairing Functions, with Applications.- Computability Theory.- NONDETERMINISM.- Nondeterministic Online Automata.- Nondeterministic FAs.- Nondeterminism in Computability Theory.- Complexity Theory.