k -synchronisierte Sequenz - k-synchronized sequence

In der Mathematik und der theoretischen Informatik ist eine k- synchronisierte Folge eine unendliche Folge von Termen s ( n ), die durch einen endlichen Automaten gekennzeichnet ist , der als Eingabe zwei Zeichenfolgen m und n nimmt , die jeweils in einer festen Basis k ausgedrückt sind , und akzeptiert, wenn m  =  s ( n ). Die Klasse der k -synchronized Sequenzen liegen zwischen den Klassen von k -Automatic Sequenzen und k -regelmäßige Sequenzen .

Definitionen

Als Beziehungen

Sei Σ ein Alphabet von k Symbolen mit k  2, und sei [ n ] _k die Basis- k- Darstellung einer Zahl n . Gegeben r  ≥ 2 ist , eine Untergruppe R von IS k -synchronized wenn die Beziehung {([ n ₁ ] _k , ..., [ n _r ] _k )} eine rechts synchronisiert rationale Beziehung über Σ ^*  × ... × Σ ^* , wobei ( n ₁ , ..., N _r ) R . ${\displaystyle \mathbb{N} ^{r}}$${\displaystyle\in}$

Sprachtheoretisch

Sei n  ≥ 0 eine natürliche Zahl und f : eine Abbildung, wobei sowohl n als auch f ( n ) in der Basis k ausgedrückt werden . Die Sequenz f ( n ) ist k -synchronized wenn die Sprache von Paaren ist regelmäßig . ${\displaystyle\mathbb{N}\rightarrow\mathbb{N}}$${\displaystyle \{(n,f(n))\}}$

Geschichte

Die Klasse der k- synchronisierten Sequenzen wurde von Carpi und Maggi eingeführt.

Beispiel

Subwortkomplexität

Gegeben eine k- automatische Folge s ( n ) und eine unendliche Kette S  =  s (1) s (2) ... sei _S (n) die Teilwortkomplexität von S ; das heißt, die Anzahl von unterschiedlichen Unterwörtern der Länge n in S . Goč, Schaeffer und Shallit zeigten, dass es einen endlichen Automaten gibt, der die Sprache akzeptiert

${\displaystyle \{(n,m)_{k}\mid n\geq 0{\text{ und }}m=\rho_{S}(n)\}.}$

Dieser Automat errät die Endpunkte jedes zusammenhängenden Symbolblocks in S und verifiziert, dass jedes Teilwort der Länge n , das innerhalb eines gegebenen Blocks beginnt, neu ist, während alle anderen Teilwörter es nicht sind. Es verifiziert dann, dass m die Summe der Größen der Blöcke ist. Da das Paar ( n ,  m ) _k von diesem Automaten akzeptiert wird, ist die Teilwortkomplexitätsfunktion der k- automatischen Folge s ( n ) k- synchronisiert.

Eigenschaften

k- synchronisierte Sequenzen weisen eine Reihe interessanter Eigenschaften auf. Eine nicht erschöpfende Liste dieser Eigenschaften ist unten aufgeführt.

• Jede k- synchronisierte Sequenz ist k- regulär .
• Jede k- automatische Sequenz ist k- synchronisiert. Genauer gesagt ist eine Folge s ( n ) genau dann k- automatisch, wenn s ( n ) k- synchronisiert ist und s ( n ) endlich viele Terme annimmt. Dies ist eine unmittelbare Folge sowohl der obigen Eigenschaft als auch der Tatsache, dass jede k- reguläre Folge mit endlich vielen Termen k- automatisch ist.
• Die Klasse der k- synchronisierten Folgen ist unter Begriffssumme und Begriffszusammensetzung abgeschlossen.
• Die Terme jeder k- synchronisierten Sequenz haben eine lineare Wachstumsrate.
• Wenn s ( n ) eine k- synchronisierte Sequenz ist, dann sind sowohl die Teilwortkomplexität von s ( n ) als auch die palindromische Komplexität von s ( n ) (ähnlich der Teilwortkomplexität, aber für unterschiedliche Palindrome ) k- reguläre Sequenzen.

Anmerkungen

Verweise

• Carpi, A.; Maggi, C. (2010), "Über synchronisierte Sequenzen und ihre Trennzeichen" , Theoret. Informatik Appl. , 35 (6): 513–524, doi : 10.1051/ita:2001129.