Kategorie-Archiv: Stickersysteme
Inhaltsangabe
Die Bausteine des Lebens sind Grundlage des theoretischen Konzeptes der Stickersysteme, das im Buch „DNA-Computing. New Computing Paradigms.“ von G. Paun, G. Rozenberg und A. Salomaa ausführlich untersucht wird. Die dort durchgeführten Komplexitätsuntersuchungen zum Vergleich von Stickersystemen und Chomskygrammatiken sind jedoch unvollständig.
In der vorliegenden Arbeit werden die genannten Untersuchungen auf Mehrkopfautomaten ausgedehnt und dadurch alle noch offenen Fragen zu Beziehungen zwischen Stickersprachfamilien und Chomskysprachfamilien beantwortet. Nebenbei werden dabei auch viele Fragen zu Beziehungen zwischen Stickersystemen und Mehrkopfautomaten, zu Beziehungen der Stickersprachfamilien untereinander und zu Abschlusseigenschaften der Stickersprachfamilien geklärt.
Diese Arbeit stellt gewissermaßen eine Ergänzung zu „DNA-Computing. New Computing Paradigms.“ dar und richtet sich hauptsächlich an Forscher, Dozenten und Studenten der Theoretischen Informatik und/oder Bioinformatik.
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.
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.
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.
Buchbestellung
Das Buch „Ausdrucksstärke von Stickersystemen. Untersuchung der Ausdrucksstärke von Stickersystemen durch Vergleich mit Chomskygrammatiken und Mehrkopfautomaten.“ wurde im Jahr 2008 im VDM Verlag veröffentlicht und ist in sämtlichen Buchläden und Online-Buch-Shops verfügbar/bestellbar. Über die folgenden Links gelangen Sie direkt zu den Bestellseiten ausgewählter Online-Buch-Shops:
Bookbutler.de
Amazon.de
bol.de
Buch.de
Buch24.de
Buecher.de
ebook.de
morebooks.de
Download
Das komplette Buch „Ausdrucksstärke von Stickersystemen. Untersuchung der Ausdrucksstärke von Stickersystemen durch Vergleich mit Chomskygrammatiken und Mehrkopfautomaten.“ (Seite 1-63, 473 KB) steht an dieser Stelle in elektronischer Form kostenfrei zum Download zur Verfügung:
Der komplette Artikel „Incomparability of simple and one-sided/regular sticker languages“ (251 KB) steht an dieser Stelle in elektronischer Form kostenfrei zum Download zur Verfügung:
Der komplette Artikel „Complexity analysis of sticker systems by means of comparison with multihead finite automata“ (274 KB) steht an dieser Stelle in elektronischer Form kostenfrei zum Download zur Verfügung:
Die Original-Diplomarbeit „Ausdrucksstärke von Stickersystemen. Untersuchung der Ausdrucksstärke von Stickersystemen durch Vergleich mit Chomskygrammatiken und Mehrkopfautomaten.“ (12.10.2004, 431 KB) steht an dieser Stelle in elektronischer Form kostenfrei zum Download zur Verfügung: