Automaten für Datenwörter : Untersuchung von Register-, Pebble- und Datenautomaten

ISBN-13: 9783639317015 / Niemiecki / Miękka / 2010 / 96 str.

Robert Strehl

Opis

In der Informatik kann man mit Hilfe von sogenannten endlichen Automaten ein reaktives System versuchen zu modellieren. Die Eingabe besteht hierbei aus einer (endlichen) Folge von Zeichen, die einem endlichen Alphabet entstammen. Als Reaktion auf die Eingabe kann der Automat Zustandswechsel ausführen. Diese Abstraktion eines Systems kann nun entscheiden, ob eine Eingabe akzeptiert oder verworfen wird. Eine mögliche Erweiterung von endlichen Automaten besteht darin, dass man das Eingabealphabet durch eine unendliche Menge von Äquivalenzklassen (hier: Datenwörter) ersetzt. Diese Erweiterung erlaubt es, ein System abzubilden, in dem das Spektrum der Eingabezeichen unbekannt oder sogar unendlich ist. Als Beispiel kann man sich ein System mit einer dynamischen Anzahl an Klienten vorstellen. Die Eingabezeichen repräsentieren hierbei gewisse Anfragen von Klienten. Der Autor Robert Strehl gibt einen einführenden Überblick über die bisher vorgestellten Automatenmodelle für Datenwörter (Register-, Pebble- und Datenautomaten), analysiert deren Ausdrucksstärke, Abschlusseigenschaften, Entscheidbarkeit und Effizienz und setzt die verschiedenen Modelle untereinander in Beziehung.

O autorze

Robert Strehl studierte Mathematik und Informatik an der Technischen Universität Dortmund. Die vorliegende Arbeit entstand am Lehrstuhl für Logik in der Informatik bei Herrn Prof. Dr. Thomas Schwentick im Rahmen des Bachelor-Studiengangs Informatik.