Problemkreis: Formale Sprachen, Endliche Automaten, Baumsprachen
Problemstellung: Im Gegensatz zu regulären Sprachen mit einfachen endlichen Wörtern, wo diverse Akzeptanzbegriffe für endliche Automaten äquivalent sind, gilt dasselbe nicht für Baumsprachen [1,2], insbesondere, wenn auch unendliche Bäume betrachtet werden. In der Diplomarbeit sollen zunächst die in der Literatur bekannten Modi des Akzeptierens gesammelt und vereinheitlicht werden. Hierauf aufbauend soll untersucht werden, ob es evtl. Hierarchien von Baumsprachenklassen gibt (wie es bei regulären Sprachen unendlicher Wörter der Fall ist [3]). Neue Baumsprachenklassen können sich evtl. auch durch Erweiterung oder Einschränkung oder neue Alternativen der Akzeptanzbegriffe ergeben. Interessant ist auch, wie weit komplexitätstheoretische Ansätze [4] hier Eingang finden.
Vorkenntnisse: Vordiplom (Grundwissen über endliche Automaten)
Literatur:
[1] F. Gecseg and M. Steiby:
Tree Automata.
Budapest, 1984.
[2] W. Thomas:
Automata on Infinite Objects.
in: J. van Leeuwen (ed.):
Formal Models and Semantics
(Handbook of Theoretical Computer Science Vol. B)
Amsterdam, 1990
[3] L. Staiger and K. Wagner:
Automatentheoretische und automatenfreie Charakterisierungen
topologischer Klassen regulärer Folgenmengen.
Elektr. Inf.verarb. Kybern. (EIK),
10 (7): 379-392, 1974
[4] A. Saoudi, D. E. Muller and P. E. Schupp:
On the Complexity of omega-Tree Sets and Nerode Theorem.
Foundations of Computer Science,
1 (1): 11-22, 1990