The pillars of computation theory. State, encoding, nondeterminism
type: Item
instance of: scholarly article
title: The pillars of computation theory. State, encoding, nondeterminism
zbMATH Open document ID: 1203.68050
DOI: 10.1007/978-0-387-09639-1
author: Arnold L. Rosenberg
published in: Universitext
publication date: 2009-11-30T00:00:00Z
review text: The abstract branch of theoretical computer science known as Computation Theory typically appears in undergraduate academic curricula in a form that obscures both the mathematical concepts that are central to the various components of the theory and the relevance of the theory to the typical student. This regrettable situation is due largely to the thematic tension among three main competing principles for organizing the material in the course. This book is motivated by the belief that a deep understanding of, and operational control over, the few ``big'' mathematical ideas that underlie Computation Theory is the best way to enable the typical student to assimilate the ``big ideas'' of Computation Theory into her daily computational life. The author charts a path by teaching the major themes that underlie all of computer science. He identifies three themes, or pillars: `state', `encoding', and `nondeterminism', which are the main ingredients of computer science in general, and, in particular, of computation theory. The author builds the elements of computation theory upon these three pillars: Chapters 3--6 are devoted to the first pillar, ``State'', Chapters 7--9 are devoted to the part ``Encoding'', and Chapters 10--13 are devoted to the part ``Nondeterminism''. Chapters 1 and 2 consist of the Introduction and the mathematical preliminaries. The author's approach singles out certain concepts and results of the three classical branches of computation theory as ``big ideas'' and, as is indicated in the author's preface, the author views this as a strength of the approach: he does go beyond these ``big ideas'' as he develops the material, so that the ``big ideas'' emerge as major signposts in a rich landscape rather than as a collection of isolated topics. In the part ``State'', the author introduces a formal model that he calls an \textit{online automaton}, which is a very abstract computational model that allows to isolate the notion of ``state''. The conceptional p…
reviewed by: M. M. Arslanov
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68-01
zbMATH DE Number: 5640403
zbMATH Keywords: Myhill-Nerode theorem
zbMATH Keywords: binary relation
zbMATH Keywords: complexity theory
zbMATH Keywords: computation theory
zbMATH Keywords: finite automata
zbMATH Keywords: nondeterministic Turing machine
zbMATH Keywords: online automata
zbMATH Keywords: space complexity
zbMATH Keywords: time complexity
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/978-0-387-09639-1
OpenAlex ID: W2490930245
description: scientific article; zbMATH DE number 5640403