Home
Curiculum Vitae
Publications
Other Writings
Book reviews
from the
Dutch Mathematical
Society
Book reviews
from the journal
Acta Applicandae
Mathematicae

Book review

Author(s) Schöning, Uwe
Title Theoretische Informatik kurz gefasst
Publisher B.I. Wiss. Verl.
Year of publication 1992
   
Reviewed by Mirela Stefanescu

A short introduction to theoretical informatics for students in informatics and mathematics is very useful now, when there are so many books concerning special branches of informatics. First part of the book is devoted to studying automata theory and formal languages. Let us remind some topics in this part: gramatics, Chomsky hierarchy, word problem, syntactic trees, the Backus-Naur form, finite automata, nondeterministic automata, equivalences and minimal automata, context free languages (normal forms, CYK-algorithm, deterministic context-free languages, context sensitive and type 0-languages).

The second part studies the computability theory: Church conjecture, Turing computabiltity, LOOP-, WHILE -, and GOTO-computability, primitively recursive and mu-recursive functions, Ackerman function , reductibility and refinement problems, Post correspondences, Gödel theorem.

As a respectable course, this ends with the complexity theory: complexity classes and P-NP-problem, NP-completeness and some solved NP-completeness problems.

A short appendix on mathematical foundations (some definitions: algebraic operations, semigroups, equivalence relations, cardinals), some comments on references and a list of literature on this subject complete the book.

The book is a good modern introductions in informatics and it is nicely printed, such that it is necessary to any library for students and specialists in informatics.