1. OPUS
  2. Universität Stuttgart
  3. 05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.18419/opus-11085
Langanzeige der Metadaten
DC ElementWertSprache
dc.contributor.authorGaißert, Marcial-
dc.date.accessioned2020-10-27T11:33:21Z-
dc.date.available2020-10-27T11:33:21Z-
dc.date.issued2020de
dc.identifier.other1736849514-
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-111024de
dc.identifier.urihttp://elib.uni-stuttgart.de/handle/11682/11102-
dc.identifier.urihttp://dx.doi.org/10.18419/opus-11085-
dc.description.abstractIn 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.de
dc.language.isodede
dc.rightsinfo:eu-repo/semantics/openAccessde
dc.subject.ddc004de
dc.titleSprachungleichungen über Forest-Sprachende
dc.title.alternativeLanguage inequalities for Forest languagesen
dc.typebachelorThesisde
ubs.fakultaetInformatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Formale Methoden der Informatikde
ubs.publikation.seiten37de
ubs.publikation.typAbschlussarbeit (Bachelor)de
Enthalten in den Sammlungen:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
SPRACHUN.PDF334,72 kBAdobe PDFÖffnen/Anzeigen
Zur Kurzanzeige


Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.