
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 BackusNaur form, finite automata, nondeterministic automata, equivalences and minimal automata, context free languages (normal forms, CYKalgorithm, deterministic contextfree languages, context sensitive and type 0languages).
The second part studies the computability theory: Church conjecture, Turing computabiltity, LOOP, WHILE , and GOTOcomputability, primitively recursive and murecursive 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 PNPproblem, NPcompleteness and some solved NPcompleteness 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.