Bibliograph. Daten | Gaißert, Marcial: Iterierte Substitutionen bei regulären Baumsprachen. Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Masterarbeit Nr. 69 (2022). 37 Seiten, deutsch.
|
Kurzfassung | Wir zeigen, dass das Beschränktheitsproblem für eine Verallgemeinerung der automata with coloring nach Bala bzw. desert automata nach Kirsten mit mehreren priorisierten Zählern und auf Bäumen in PSPACE ist. Dieses Ergebnis nutzen wir, um zu zeigen, dass in doppelt exponentieller Zeit auf einer nichtdeterministischen Turingmaschine entschieden werden kann, ob eine endliche lineare Substitution σ mit σ(L)=R für gegebene reguläre Baumsprachen L und R existiert.
|
Volltext und andere Links | Volltext
|
Abteilung(en) | Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
|
Betreuer | Kufleitner, PD Dr. Manfred |
Eingabedatum | 17. März 2023 |
---|