Automatentheorie und Logik [Paperback]

Das Buch besch?ftigt sich mit der Theorie endlicher Automaten und den klassischen Resultaten wie den S?tzen von Richard B?chi und Michael Rabin. Die vier Teile des Buchs sind den unterschiedlichen Strukturen gewidmet: endliche W?rter, B?ume, endliche und unendliche B?ume. Jeder Teil endet mit ?bungsaufgaben zum behandelten Stoff sowie Hinweisen auf weiterf?hrende Literatur. Soweit Vorkenntnisse zur Theorie formaler Sprachen vorhanden sind, kann das Buch ohne weitere Hilfsmittel durchgearbeitet werden.

Teil I Endliche W?rter.- 1 Grundlagen der Theorie formaler Sprachen.- 2 Schwache, monadische Logik zweiter Stufe.- 3 Alternierende, endliche Automaten.- 4 Sternfreie Sprachen.- Teil II Unendliche W?rter.- 5 Automaten auf unendlichen W?rtern.- 6 Komplementierung von B?chi-Automaten.- 7 Weitere Akzeptanzbedingungen.- 8 Determinisierung von B?chiautomaten.- 9 Entscheidungsverfahren f?r !-Automaten.- !-Automaten.- 10 Alternierende Automaten.- 11 Linearzeit-Temporale Logik.- Teil III Endliche B?ume.- 12 Automaten auf endlichen B?umen.- 13 Anwendungen.- Teil IV Unendliche B?ume.- 14 Automaten auf unendlichen B?umen.- 15 Komplement-Abschluss und Leerheitsproblem.- 16 Logiken auf unendlichen B?umen.

From the reviews:

It is self-contained with respect to automata theory in that all necessary notions and results from an elementary course in automata and formal language theory are compiled in the first chapter in order to give a coherent account of the subject. & A subject index and a good list of references complete the book. This is a very good advanced textbook. It has a high standard, is written with mathematical rigour, and is & very clear in its exposition. (Klaus D. Kiermeier, Zentralblatt MATH, Vol. 1257, 2013)

Prof. Dr. Martin Lange, lehrt an der Universit?t Kassel, Fachbereich Elektronik/Informatik, Germany

Prof. Dr. Martin Hofmann, lehrt an der Ludwig-Maximilians-Universit?t M?nchen, Inslƒ"