Konferenzbeitrag
Generalisierte Synchronisation endlicher Automaten
Lade...
Volltext URI
Dokumententyp
Text/Conference Paper
Dateien
Zusatzinformation
Datum
2023
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik e.V.
Zusammenfassung
Endliche Automaten begegnen uns u ̈berall im Alltag, von der Steuerung der Kaffeemaschine über den Aufzug bis hin zu autonomen Systemen. Synchronisierende Wörter agieren hierbei als ein Software-Reset, eine Sequenz von Befehlen, die den Automaten von jedem Zustand aus in den gleichen Zustand überführt. Hierbei ist es wünschenswert eine gewisse Kontrolle u ̈ber die Aktionen eines synchronisierenden Wortes zu behalten. Wir untersuchen daher die Komplexität der Frage, ob ein endlicher Automat ein synchronisierendes Wort besitzt, unter verschiedenen Einschränkungen, wie beispielsweise, dass das Wort aus einer bestimmten Sprache stammen muss, oder, dass die Sequenz der durchlaufenen Zustände eingeschränkt wird. Anschließend generalisieren wir das Konzept synchronisierender Automaten auf das mächtigere Berechnungsmodell des Kellerautomatens. Im letzten Teil der Arbeit untersuchen wir, inwiefern sich ein endlicher Automat vereinfachen lässt, indem wir die akzeptierte Sprache eines Automatens in den Schnitt simplerer Sprachen zerlegen.