x(-87) = .. = x(-1) = True
forall k >= 0: x(k) = NAND ( x(k-22), x(k-34), x(k-53), x(k-87) )
hat Vorperiode 314 und Periode 114109.)
Jede solche NAND-Folge ist die Gewinn/Verlust-Bewertung für Positionen in einem Subtraktionsspiel. (In dem Spiel subtrahieren beide Spieler abwechselnd von der aktuellen Zahl k eine der Zahlen 22, 34, 53 oder 87, und wer nicht mehr ziehen kann, weil die Differenz < 0 wird, verliert.)
Subtraktionsspiele sind Wort-Ersetzungs-Spiele, im Beispiel für die Regelmenge
{ a^22 -> a^0, a^34 -> a^0, a^52 -> a^0, a^87 -> a^0 }.
Weil die o. g. Bitfolge periodisch ist, ist für solche Spiele die Menge aller Verlustpositionen eine reguläre Sprache (über einem ein-buchstabigen Alphabet).
Man kann nun ganz allgemein die Aufgabe betrachten, Gewinn-Mengen für Wort- und Term-Ersetzungs-Spiele formalsprachlich zu beschreiben.
Im Vortrag präsentiere ich einige Methoden, Ergebnisse und offene Fragen zu diesem Thema. Grundkenntnisse über endliche Automaten sind zum Verständnis ausreichend. Die offenen Fragen können gern im Rahmen eines Praktikums-, Bachelor- oder Diplomthemas bearbeitet werden.
Beschreibe die Menge der Verlustpositionen für das Term-Ersetzungs-Spiel über der Signatur { F nullstellig, T nullstellig, C zweistellig } mit Regelmenge
{ F -> T, C(F, T) -> F }