Die Holonomie-Zerlegung von Automaten

Abstract

Diese Diplomarbeit beschäftigt sich mit einer intuitiven, aber trotzdem möglichst kompakten Darstellung der Holonomie-Zerlegung von Automaten, die ausschließlich elementare Mittel nutzt. Durch die Formulierung des Problems als Graph konnten bisherige Beweise vereinfacht werden, sodass nur noch Überdeckungen, statt relationalen Überdeckungen, benötigt werden. Neu ist, dass der hier gegebene Beweis sogar konstruktiv statt induktiv ist. Die graphentheoretische Formulierung ermöglicht eine einfache Abschätzung der Faktorzahl einer vollständigen, sogenannten Krohn-Rhodes-Zerlegung.