Automatentheorie und Logik
Das Buch beschäftigt sich mit der Theorie endlicher Automaten auf endlichen und unendlichen Wörtern sowie Bäumen. Es behandelt klassische Resultate wie die Sätze von Büchi und Rabin, die zeigen, wie sich monadische Logiken 2. Stufe auf diesen Strukturen m
- PDF / 4,175,816 Bytes
- 234 Pages / 439.37 x 666.142 pts Page_size
- 24 Downloads / 183 Views
eXamen.press ist eine Reihe, die Theorie und Praxis aus allen Bereichen der Informatik für die Hochschulausbildung vermittelt.
Martin Hofmann · Martin Lange
Automatentheorie und Logik
123
Prof. Dr. Martin Hofmann Ludwig-Maximilians-Universität München Institut für Informatik Theoretische Informatik Oettingenstraße 67 80538 München Deutschland [email protected]
Prof. Dr. Martin Lange Universität Kassel Fachbereich Elektrotechnik und Informatik Wilhelmshöher Allee 71 34121 Kassel Deutschland
ISSN 1614-5216 ISBN 978-3-642-18089-7 e-ISBN 978-3-642-18090-3 DOI 10.1007/978-3-642-18090-3 Springer Heidelberg Dordrecht London New York Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar. c Springer-Verlag Berlin Heidelberg 2011 Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte, insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. September 1965 in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Einbandentwurf: KuenkelLopka GmbH Gedruckt auf säurefreiem Papier Springer ist Teil der Fachverlagsgruppe Springer Science+Business Media (www.springer.com)
V
Vorwort Dieses Buch geht zur¨ uck auf eine Vorlesung namens “Automatentheorie”, die von uns erstmals und gemeinsam im Sommersemester 2004 an der LudwigMaximilians-Universit¨ at M¨ unchen f¨ ur Studenten im Hauptstudium der damaligen Diplom-Studieng¨ ange Informatik und Mathematik gehalten wurde. Aufgrund des Interesses, auf das diese Veranstaltung bei den Teilnehmern gestoßen war, wurde die Vorlesung in den Sommersemestern 2006, 2008 und 2010 wieder angeboten. Aus anf¨ anglichen, handschriftlichen Unterlagen entstand in diesen Zeiten ein aush¨ andigbares Vorlesungsskript, welches bei jeder Wiederholung der Veranstaltung weiter u ¨berarbeitet wurde und am Ende nun zu diesem Buch geworden ist. Es ist daher nicht verwunderlich, dass dieses Buch als Grundlage f¨ ur eine Vorlesung im Bereich der theoretischen Informatik, typischerweise als Modul in einem Master-Studiengang, gedacht ist. Der hier pr¨asentierte Stoff eignet sich, um eine Vorlesung mit 4 Semesterw
Data Loading...
