K-synchronizovaná sekvence - K-synchronized sequence

v matematika a teoretická informatika, a k-synchronizovaná sekvence je nekonečný sekvence podmínek s(n) charakterizovaný a konečný automat brát jako vstup dva řetězce m a n, každý vyjádřený v některých fixních základna k, a přijetí, pokud m = s(n). Třída k-synchronizované sekvence leží mezi třídami k-automatické sekvence a k-pravidelné sekvence.

Definice

Jako vztahy

Nechť Σ je abeceda k symboly kde k ≥ 2 a nechte [n]_k označit základnuk zastoupení nějakého čísla n. Dáno r ≥ 2, podmnožina R z ${ displaystyle mathbb {N} ^ {r}}$ je k-synchronizováno, pokud relace {([n₁]_k, ..., [n_r]_k)} je synchronizován vpravo^[1] racionální vztah přes Σ^∗ × ... × Σ^∗, kde (n₁, ..., n_r) ${ displaystyle in}$ R.^[2]

Jazyková teoretika

Nechat n ≥ 0 je přirozené číslo a nechte F: ${ displaystyle mathbb {N} rightarrow mathbb {N}}$ být mapou, kde obojí n a F(n) jsou vyjádřeny v základu k. Sekvence F(n) je k-synchronizováno, pokud je jazyk párů ${ displaystyle {(n, f (n)) }}$ je pravidelný.

Dějiny

Třída k-synchronizované sekvence představili Carpi a Maggi.^[2]

Příklad

Složitost podslovu

Vzhledem k tomu, k-automatická sekvence s(n) a nekonečný řetězec S = s(1)s(2) ..., nechť ρ_S(n) označuje složitost podslovu S; tj. počet odlišných podřízená slova délky n v S. Goč, Schaeffer a Shallit^[3] prokázal, že existuje konečný automat přijímající jazyk

${ displaystyle {(n, m) _ {k} mid n geq 0 { text {and}} m = rho _ {S} (n) }.}$

Tento automat odhaduje koncové body každého sousedícího bloku symbolů S a ověří, že každý podslov délky n začínat v daném bloku je nové, zatímco všechna ostatní dílčí hesla nejsou. Poté to ověří m je součet velikostí bloků. Protože dvojice (n, m)_k je tímto automatem přijímán, funkce složitosti podslovu k-automatická sekvence s(n) je k-synchronizované.

Vlastnosti

k-synchronizované sekvence vykazují řadu zajímavých vlastností. Níže je uveden neúplný seznam těchto vlastností.

• Každý k-synchronizovaná sekvence je k-pravidelný.^[4]
• Každý k-automatická sekvence je k-synchronizované. Abych byl přesný, sekvence s(n) je k-automatické právě tehdy s(n) je k-synchronizované a s(n) přijímá konečně mnoho pojmů.^[5] To je okamžitý důsledek jak výše uvedené vlastnosti, tak skutečnosti, že každý k-pravidelná sekvence s konečně mnoha pojmy je k-automatický.
• Třída k-synchronizované sekvence jsou uzavřeny pod termwise součtem a termwise složení.^[6][7]
• Podmínky jakékoli k-synchronizovaná sekvence má lineární rychlost růstu.^[8]
• Li s(n) je k-synchronizovaná sekvence, pak složitost podslovu s(n) a palindromická složitost s(n) (podobný složitosti podslov, ale odlišný palindromy ) jsou k-pravidelné sekvence.^[9]

Poznámky

Reference

• Carpi, A .; Maggi, C. (2010), „Synchronizované sekvence a jejich oddělovače“, Teoretická. Aplikovaná informatika, 35 (6): 513–524, doi:10.1051 / ita: 2001129.