Introduction to theoretical computer science. Foundations and models (Q1336487)

This is a thorough introductory text-book to the theoretical foundations of informatics. The first of the eighth chapters (Mathematische Grundlagen) contains the most fundamental concepts on sets, functions and words (of finite length over a finite alphabet). Random access machines and two simplified versions of the programming language PASCAL are discussed in Chapter 2 (Modelle der Computer-Berechenbarkeit), it is proved that the computational power of these three models is the same. In Chapter 3 (Andere Berechenbarkeitsmodelle) the Turing machines and the partial recursive functions are introduced, the fact that all computational models studied till now are essentially equivalent leads to the celebrated (intuitive) principle called Church's thesis. Two subclasses of the class of all sets consisting of natural numbers are considered in Chapter 4 (Entscheidbarkeit und Aufzählbarkeit): the class of decidable sets and the class of recursively enumerable sets; it is shown, among others, that \(\mathcal A\) is decidable exactly when \(\mathcal A\) and its complement are recursively enumerable. Three classes (constituting an ascending hierarchy) consisting of decidable sets are the subject of Chapter 5 (Berechnungskomplexität), depending on the polynomial or nondeterministically polynomial or exponential complexity of the decision procedure. An NP-complete set is analyzed and the reader becomes acquainted with the open problem whether the first of these classes is properly included in the second one. From the content of Chapter 6 (Boolesche Funktionen), let the listing of all Boolean functions of at most two variables, the characterization of functional completeness due to Post and the notion of combinatorial circuit be mentioned. Chapter 7 (Endliche Automaten) deals with finite automata (mostly in the sense of Mealy) and with logical circuits, the chapter culminates in Kleene's theorem asserting that precisely the regular sets (of input words) can be represented by recognizer-type automata. Again an ascending hierarchy is studied in the last chapter (Grammatiken und Formale Sprachen): the classes of context-free languages and context-sensitive ones, furthermore the most comprehensive concept of formal language, as these have been introduced by Chomsky. Also the connection between context-free languages and nondeterministic pushdown automata is shown.