Masterarbeit MSTR-2019-67

Bibliograph.
Daten
Bühler, Andreas: Das Ordnungsproblem für Automatengruppen und verwandte Fragestellungen.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Masterarbeit Nr. 67 (2019).
25 Seiten, deutsch.
Kurzfassung

In dieser Arbeit werden Problemstellungen in der Klasse der Automatenhalbgruppen untersucht. Ein besonderer Augenmerk gilt dabei dem Ordnungsproblem welches im Allgemeinen sowohl für Automatenhalbgruppen als auch für Automatengruppen unentscheidbar ist. Es wird dann für die Klasse der Automatenhalbgruppen mit beschränkter Aktivität ein Algorithmus mit überraschend geringem Platzbedarf vorgestellt. Danach wird ein Entscheidungsalgorithmus für das Mitgliedschaftsproblem in ultimativ periodischen Teilmengen von Automatenhalbgruppen beschränkter Aktivität erarbeitet. Dieses Problem beinhaltet insbesondere das Mitgliedschaftsproblem in monogenen Unterhalbgruppen, welches dadurch ebenfalls in Automatenhalbgruppen beschränkter Aktivität entscheidbar ist.

Volltext und
andere Links
Volltext
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
BetreuerDiekert, Prof. Volker, Wächter, Jan Philipp
Eingabedatum19. Februar 2020
   Publ. Institut   Publ. Informatik