Wortdifferenzen

Beschreibung

Die Wortdifferenzen sind eine endliche Menge einer Gruppe mit Reisegefährteneigenschaft, die uns erlaubt, die Gruppe in einen Automaten zu verwandeln.

Definition

In einer Gruppe mit der Reisegefährteneigenschaft bzgl Konstante $k$ gilt für zwei Wörter $w,v$, deren Evaluationen Abstand maximal $1$ haben, dass das Wort $\psi (t)=w(t{)}^{-1}v(t)$ für alle $t$ kürzer ist als $k$. ($w(t)$ ist der Präfix von Länge $t$ des Wortes $w$) Für alle Wahlen von $v,w$ liegen die $\psi (t)$ damit in einer Endlichen Menge $\mathcal{D}$, die Wortdifferenzen

Eigenschaften

Satz:

lit_parkerMappingClassGroup2004