Bibliography | Seybold, Martin P.: Die Holonomie-Zerlegung von Automaten. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 3332 (2012). 27 pages, german.
|
CR-Schema | F.4.3 (Formal Languages)
|
Keywords | Automaten,Halbgruppen,Holonomie-Zerlegung,Krohn-Rhodes-Zerlegung |
Abstract | 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.
|
Full text and other links | PDF (304719 Bytes)
|
Contact | martin.seybold@gmx.de |
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
|
Superviser(s) | Manfred Kufleitner |
Entry date | August 14, 2012 |
---|