Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-12684
| Autor(en): | Gaißert, Marcial |
| Titel: | Iterierte Substitutionen bei regulären Baumsprachen |
| Erscheinungsdatum: | 2022 |
| Dokumentart: | Abschlussarbeit (Master) |
| Seiten: | 37 |
| URI: | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-127036 http://elib.uni-stuttgart.de/handle/11682/12703 http://dx.doi.org/10.18419/opus-12684 |
| Zusammenfassung: | 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. |
| Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
| Datei | Beschreibung | Größe | Format | |
|---|---|---|---|---|
| MA_Gaißert_MA.pdf | 874,75 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.