Historie

Im Jahr 2003 näherte sich das am 01. September 1999 begonnene Studium der Informatik an der Martin-Luther-Universität Halle-Wittenberg seinem Ende entgegen und ich begab mich auf die Suche nach einem Diplomthema.

Vertiefungsrichtung und die Diplomarbeit sollten natürlich zu dem späteren beruflichen Werdegang passen. Und da ich in die freie Wirtschaft wollte, favorisierte ich eher praktische Themen, obwohl mir die Theorie immer am meisten gefallen hat.

Die mir angebotenen Themen in den potentiellen Vertiefungsrichtungen „Parallele Programmierung“ und „Effiziente Datenstrukturen und -algorithmen“ haben mir jedoch nicht zugesagt. Somit beschloss ich, meiner Intuition zu folgen und „Theoretische Informatik“ als Vertiefungsrichtung zu wählen.


Es fehlte mir jedoch noch ein Schein, und ein Diplomthema hatte ich ja auch noch nicht. Daher besuchte ich im Wintersemester 2003/2004 die Vorlesung „DNA-Computing“, gehalten von Doz. Dr. Dietrich Kuske.

Hier lernten wir Studenten das Konzept der Stickersysteme kennen und erfuhren, dass noch einige wichtige Beziehungen ungeklärt seien. Sollten wir tatsächlich eine solche ungeklärte Beziehung beantworten und eine stichhaltige Beweisidee präsentieren können, so wäre das ein unterstützenswertes Diplomthema, so unser Dozent.


Tatsächlich fand ich sehr schnell den Beweis, dass die Stickersprachfamilie echt schmächtiger ist, als die Familie der kontextsensitiven Sprachen. Der Beweis beruht auf der Simulation von Stickersystemen durch Vierkopfautomaten. Das Konzept der Mehrkopfautomaten gehört zu den Grundlagen der Theoretischen Informatik und wurde in den 1970/80er Jahren intensiv erforscht. Die Ergebnisse werden auch heute noch genutzt, das Konzept selber gerät aber langsam in Vergessenheit und wird kaum noch gelehrt – eine Ausnahme ist Prof. Dr. Staiger an der Martin-Luther-Universität Halle-Wittenberg.


Das Diplomthema war gefunden, die Prüfer (Doz. Dr. Kuske und Prof. Dr. Staiger) ebenfalls und das erste Hauptresultat stand fest, es konnte also losgehen: Im Sommersemester 2004 erarbeitete ich die Hintergründe/Grundlagen, optimierte die gefundene Beweisidee, entwickelte einen vollständigen Beweis und konnte noch viele weitere wichtige (bisher ungeklärte) Aussagen klären, z.B. konnte belegt werden, dass es reguläre Sprachen gibt, die nicht zur Familie der einfachen Stickersprachen gehören können (zweites Hauptresultat).

Das Ergebnis meiner halbjährigen und durch Doz. Dr. Kuske und Jens Keilwagen unterstützten Forschungen konnte im Oktober 2004 termingerecht abgegeben und im Anschluss mit der Note „sehr gut“ bewertet werden.

Ausdrucksstärke von Stickersystemen. Untersuchung der Ausdrucksstärke von Stickersystemen durch Vergleich mit Chomskygrammatiken und Mehrkopfautomaten. Peter Weigel. Diplomarbeit, Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, Halle/Saale, 12.10.2004.


Ende 2004 übersetzten dann Jens Keilwagen und ich die beiden Hauptresultate der Diplomarbeit in die englische Sprache und starteten Anfang 2005 einen Fachpublikationsversuch des zweiten Hauptresultates bei Elsevier Science.

Complexity analysis of sticker systems by means of comparison with multihead finite automata. Peter Weigel. Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, Halle/Saale, Februar 2005.

Incomparability of simple and one-sided/regular sticker languages. Peter Weigel. Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, Halle/Saale, Februar 2005.

Die Arbeit wurde jedoch abgelehnt, mit Verweis auf die bereits existierende Arbeit Nikè van Vugt. Models of Molecular Computing. Ph.D. Thesis, Universiteit Leiden, May 2002. ISBN 90-77017-67-4 / 978-9-077-01767-8, die den Beweis des zweiten Hauptresultates in einer schwächeren Version mit gleicher Beweisidee enthält (siehe Lemma 8.2).

Der Versuch der Publikation wurde daraufhin komplett eingestellt, zumal der Wahrscheinlichkeit sehr hoch eingeschätzt werden musste, dass es für das erste Hauptresultat ebenfalls ähnliche Beweisideen gibt. (Die gerade genannte Arbeit stellt bereits Verbindungen zwischen Stickersystemen und Blind-Counter-Automaten her, der Übergang zu Mehrkopfautomaten ist da nur noch minimal.)


Im Jahr 2008 trat dann der VDM Verlag an mich heran, mit der Bitte meine Diplomarbeit veröffentlichen zu dürfen.

Die Diplomarbeit wurde daraufhin um nachträglich gefundene bis dato aber nicht eingearbeitete Beweise ergänzt und insgesamt aktualisiert. Im Juli 2008 wurden die aktualisierte Diplomarbeit dann im VDM Verlag als Buch veröffentlicht.

Am Ende des Jahres 2009 wurde dann zu Marketing- und Vertriebszwecken diese Internetpräsenz aufgebaut und Anfang 2018 komplett modernisiert.

Posted in Stickersysteme.