Diploma Thesis DIP-3017

BibliographyKlein, Kim-Manuel: Das Verhalten von Traversierenden Baumautomaten mit Marken.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 3017 (2010).
23 pages, german.
CR-SchemaF.1.1 (Models of Computation)
Abstract

Traversierende Baumautomaten wurden bereits 1971 von Aho und Ullman untersucht. Die Berechnungsstärke dieses Modells konnte jedoch erst in den letzten Jahren besser eingeordnet werden und mit klassischen Baumautomaten-Modellen verglichen werden.

Um die Ausdrucksmächtigkeit von traversierenden Baumautomaten weiter zu erhöhen, kann man verschiedene Mechanismen zur Verwendung von Marken hinzufügen. Das Verhalten hierbei unterscheidet sich vor allem dadurch, ob man eine gelegte Marke nur von der Position der Marke aus oder von einer beliebigen Position aus wieder entfernen darf. Im ersten Fall spricht man von strikten und im zweiten Fall von schwachen Automaten.

Bojanczyk, Samuelides, Schwentick und Segoufin konnten 2006 zeigen, dass strikte und schwache traversierende Baumautomaten gleich mächtig sind. In der Diplomarbeit soll die dabei verwendete Konstruktion näher untersucht werden. Das Hauptziel ist es, die dabei auftretenden Schranken für die Größe der Automaten zu verbessern.

Full text and
other links
PDF (187133 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Kufleitner, Manfred
Entry dateNovember 18, 2010
   Publ. Computer Science