Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-11217
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKotowsky, Maximilian-
dc.date.accessioned2021-01-07T15:31:20Z-
dc.date.available2021-01-07T15:31:20Z-
dc.date.issued2020de
dc.identifier.urihttp://elib.uni-stuttgart.de/handle/11682/11234-
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-112345de
dc.identifier.urihttp://dx.doi.org/10.18419/opus-11217-
dc.description.abstractEndliche Automaten sind für viele Bereiche der Informatik von enormer Bedeutung. Neben den praktischen Anwendungen dieser Maschinenmodelle sind vor allem die, von ihnen erzeugten Automaten(halb)gruppen und ihre algebraischen sowie algorithmischen Eigenschaften von Interesse für die theoretische Informatik. Die Klassifizierung von Automatengruppen nach ihrer Aktivität durch Said N. Sidki und später durch Bartholdi et al. ermöglicht zusätzlich eine spezifischere Untersuchung dieser Eigenschaften. Die Aktivität ist hierbei das Wachstum der Sprache der Wörter, auf denen ein Automat nichttrivial operiert. In dieser Arbeit gehen wir vor allem auf die Komplexität des (uniformen) Wortproblems von Automatengruppen finitärer und Automatenmonoiden beschränkter Aktivität ein. Weiterhin ordnen wir eine Variante des uniformen Wortproblems, das komprimierte uniforme Wortproblem von Automatengruppen finitärer Aktivität, komplexitätstheoretisch ein. Dazu erweitern wir einen Beweis von Volodymyr V. Nekrashevych und Ievgen V. Bondarenko auf Automatenmonoide und zeigen, dass jedes Automatenmonoid beschränkter Aktivität auch kontrahierend ist. Basierend hierauf ist es möglich, das Wortproblem dieser Automatenmonoide in deterministisch logarithmischem Platz zu entscheiden. Für den Beweis der coNP-Vollständigkeit des uniformen Wortproblems finitärer Automatengruppen nutzen wir die Technik der balancierten Kommutatoren, die ursprünglich von Anatolij I. Mal'cev eingeführt und von David A. Mix Barrington verwendet wurde. Dieses Resultat kann direkt auf Automatengruppen beschränkter Aktivität übertragen werden und zeigt, dass das uniforme Wortproblem dieser Automatenklasse coNP-schwer ist. Schließlich betrachten wir das komprimierte uniforme Wortproblem finitärer Automatengruppen, bei dem das Zustandswort durch ein sogenanntes Straight-Line-Programm, also eine deterministisch kontextfreie Grammatik die nur ein Wort erzeugt, eingegeben wird. Analog zum vorangegangenen Beweis verwenden wir hier die Technik der balancierten Kommutatoren um zu zeigen, dass das genannte Problem PSPACE-vollständig ist.de
dc.language.isodede
dc.rightsinfo:eu-repo/semantics/openAccessde
dc.subject.ddc004de
dc.titleDas uniforme Wortproblem für Automatengruppen beschränkter Aktivitätde
dc.title.alternativeThe uniform word problem for automata groups of bounded activityen
dc.typebachelorThesisde
ubs.fakultaetInformatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Formale Methoden der Informatikde
ubs.publikation.noppnyesde
ubs.publikation.seiten41de
ubs.publikation.typAbschlussarbeit (Bachelor)de
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
Bachelorarbeit_MaximilianKotowsky.pdf283,2 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.