| Bibliography | Gaißert, Marcial: Iterierte Substitutionen bei regulären Baumsprachen.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 69 (2022).
37 pages, german.
|
|---|
| Abstract | 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.
|
|---|
Full text and
other links | Volltext
|
|---|
| Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
|
|---|
| Superviser(s) | Kufleitner, PD Dr. Manfred |
|---|
| Entry date | March 17, 2023 |
|---|