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)
- Quellen
- Lothair: Combinatorics on Words, Cambridge Univ. Press 1997, http://www-igm.univ-mlv.fr/~berstel/Lothaire/
- Waldmann: Skript 2000, http://www.imn.htwk-leipzig.de/~waldmann/edu/ancient/ss00/kombinat/