Diploma Thesis DIP-3141

BibliographyWalter, Tobias: Über die Billaudsche Vermutung.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 3141 (2011).
35 pages, german.
CR-SchemaF.4.3 (Formal Languages)
G.2.1 (Discrete Mathematics Combinatorics)
Abstract

Diese Arbeit thematisiert die Billaudsche Vermutung. Diese handelt von einer Induktivität von Fixpunktwörtern, Wörtern, die Fixpunkte nicht-trivialer Morphismen sind. Billaud stellte 1993 in der Newsgroup comp.theory seine Vermutung auf. Seitdem konnte wenig zur Vermutung veröffentlicht werden.

In dieser Arbeit wird zunächst die Vermutung auf kleiner Alphabetgröße untersucht. Dabei wird die Vermutung auf drei Buchstaben bewiesen und Teilresultate der Vermutung auf vier Buchstaben erzielt. Der zweite Teil der Arbeit beschäftigt sich mit einer schwächeren Vermutung und beweist diese teilweise.

Full text and
other links
PDF (406351 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Nowotka, Dirk
Entry dateAugust 22, 2011
   Publ. Computer Science