Bibliograph. Daten | Seybold, Martin P.: Die Holonomie-Zerlegung von Automaten. Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Diplomarbeit Nr. 3332 (2012). 27 Seiten, deutsch.
|
CR-Klassif. | F.4.3 (Formal Languages)
|
Keywords | Automaten,Halbgruppen,Holonomie-Zerlegung,Krohn-Rhodes-Zerlegung |
Kurzfassung | Die Holonomie-Zerlegung von Automaten Martin P. Seybold
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.
|
Volltext und andere Links | PDF (304719 Bytes)
|
Kontakt | martin.seybold@gmx.de |
Abteilung(en) | Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
|
Betreuer | Manfred Kufleitner |
Eingabedatum | 14. August 2012 |
---|