Beschreibung
Die Reisegefährteneigenschaft ist eine mögliche Eigenschaft einer Gruppe.
Definition
Sei eine Gruppe generiert durch . Sie erfüllt die Reisegefährteneigenschaft, wenn es eine Konstante gibt, sodass alle zwei Wörter über , die fast als das gleiche Gruppenelement evaluieren (d.h. ) Reisegefährten sind.
Ich finde bisschen komisch, das man hier fast das gleiche Element und nicht genau das gleiche Element fordert. Ich würde ehrlich gesagt, echt gerne mal beispiele sehen. Ich kann mir gerade nicht so viel vorstellen
Eigenschaften
Satz: Abschätzung der Präfixlängen
In einer Gruppe mit der Reisegefährteneigenschaft kann man eine einfache Abschätzung für die Entfernung zweier Präfixe finden. Seien zwei Wörter mit Entfernung maximal . Dann hat (gekürzt) eine Länge kleiner .