Kaskadenzerlegung spezieller Automatenklassen

Abstract

Der Begriff des endlichen Automaten spielt für die Informatik eine große Rolle. Vom Chip-Design über die Progammimplementierung bis hin zur Sprach- und Automatentheorie findet er Anwendung. Dies ist Grund genug sich mit endlichen Automaten genauer zu beschäftigen. Auf algebraischer Seite ist der endliche Automat eng verwandt mit der Halbgruppe oder dem Monoid. Zwar sind diese Konzepte weniger anschaulich als ein endlicher Automat, sie erlauben jedoch einen anderen Blickwinkel und machen die mathematische Betrachtung an einigen Stellen einfacher.

Durch das Krohn-Rhodes-Theorem ist bekannt, dass sich eine beliebige endliche Halbgruppe in einfache Gruppen und FlipFlops zerlegen lasst. Die Rückkopplungsfreiheit dieser Zerlegung motiviert den Begriff der "Kaskadenzerlegung". Während die einfachen Gruppen, die dabei auftreten, in der ursprünglichen Halbgruppe selbst enthalten sind, ist dies beim FlipFlop nicht notwendigerweise der Fall. Es stellt sich daher die Frage: Gibt es eine Menge von strukturell möglichst einfachen Halbgruppen, die als Bausteine eine Zerlegung jeder – auch komplexeren – Halbgruppe so ermöglichen, dass jeder verwendete Baustein in der Halbgruppe selbst enthalten ist? Ist die Menge endlich und wie funktioniert die Zerlegung? Angetrieben durch diese Fragestellung werden in dieser Arbeit Zerlegungen von Halbgruppen und Monoiden aus speziellen Klassen genauer untersucht, für die die Frage nach den Bausteinen beantwortet werden kann.