Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-11085
| Autor(en): | Gaißert, Marcial |
| Titel: | Sprachungleichungen über Forest-Sprachen |
| Sonstige Titel: | Language inequalities for Forest languages |
| Erscheinungsdatum: | 2020 |
| Dokumentart: | Abschlussarbeit (Bachelor) |
| Seiten: | 37 |
| URI: | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-111024 http://elib.uni-stuttgart.de/handle/11682/11102 http://dx.doi.org/10.18419/opus-11085 |
| Zusammenfassung: | In dieser Arbeit untersuchen wir die Komplexität des Äquivalenzproblems und des Teilmengenproblems für Forests, jeweils auch unter Substitutionen, auf Eingabe der in [BW07] definierten Forest-Algebren und Forest-Automaten. Hierbei stehen im Zentrum dieser Arbeit Äquivalenz- und Teilmengenprobleme unter Substitutionen an den Blättern der Forests, für die wir Vollständigkeit für verschiedene Klassen in der Polynomialzeithierarchie sowie in einem Fall für DP zeigen. Für Substitutionen an inneren Knoten zeigen wir P-Vollständigkeit bei gegebener Substitution sowie in einem Fall PSPACE-Schwierigkeit für die Frage der Existenz einer (I_oi-)Substitution. |
| Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
| Datei | Beschreibung | Größe | Format | |
|---|---|---|---|---|
| SPRACHUN.PDF | 334,72 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.