Kombinatorik auf Wörtern (2 * 90 min)


Johannes Waldmann im VL 2010

  • Paperfolding sequence
    • mechanische Definition (Falten)
    • p_{n+1} = p_n 1 reverse(flip(p_n)
    • p_{n+1} = merge (1010.. , p_n}
    • p als codierter Fixpunkt eines uniformen Morphismus (betrachte 2-er Gruppen von Bits)
    • Berechnung eines Folgengliedes aus Binärdarstellung des Index (m.a.W: p ist eine automatische Folge)

  • Fibonacci-Wort
    • f_{n+2} = f_{n+1} f_n
    • f = phi^omege 0 für phi : 0 -> 01, 1 -> 0
    • f als mechanisches Wort (Treppenlinie approximiert Gerade)
    • f enthält beliebig lange Palindrome

  • vermeidbare Muster
    • t = Fixpunkt von 0 -> 01, 1 -> 10 vermeidet overlaps (xyxyx) und damit Kuben
    • m = Fixpunkt von 0 -> 012, 1 -> 02, 2 -> 1 vermeidet Quadrate (Beweis: t = h(m) für geeigneten Morphismus h)