K-pravidelná sekvence - K-regular sequence
v matematika a teoretická informatika, a k-pravidelná posloupnost je sekvence splňující lineární rekurenční rovnice, které odrážejí základna-k reprezentace celých čísel. Třída k-pravidelné sekvence zobecňují třídu k-automatické sekvence na abecedy nekonečné velikosti.
Definice
Existuje několik charakterizací k-pravidelné sekvence, které jsou všechny ekvivalentní. Některé běžné charakterizace jsou následující. Pro každého bereme R′ Být a komutativní Noetherian ring a vezmeme R být a prsten obsahující R′.
k-jádro
Nechat k ≥ 2. The k-jádro sekvence je sada podsekcí
Sekvence je (R′, k) -regular (často zkráceno na "k-regular "), pokud -modul generovaný K.k(s) je konečně vygenerovaný R′-modul.[1]
Ve zvláštním případě, když , sekvence je -pravidelné, pokud je obsažen v konečně-dimenzionálním vektorovém prostoru .
Lineární kombinace
Sekvence s(n) je k-pravidelné, pokud existuje celé číslo E takové, že pro všechny Ej > E a 0 ≤ rj ≤ kEj - 1, každá posloupnost s formuláře s(kEjn + rj) je vyjádřitelný jako R′-lineární kombinace , kde Cij je celé číslo, Fij ≤ Ea 0 ≤ bij ≤ kFij − 1.[2]
Alternativně sekvence s(n) je k-pravidelné, pokud existuje celé číslo r a subsekvence s1(n), ..., sr(n) takové, že pro všechny 1 ≤ i ≤ r a 0 ≤ A ≤ k - 1, každá sekvence si(kn + A) v k-jádro K.k(s) je R′ -Lineární kombinace subsekvencí si(n).[2]
Formální série
Nechat X0, ..., Xk − 1 být soubor k nepřeměňující proměnné a nechť τ je mapa posílající nějaké přirozené číslo n do řetězce XA0 ... XAE − 1, kde základna-k zastoupení X je řetězec AE − 1...A0. Pak sekvence s(n) je k-pravidelné právě tehdy, když formální série je -Racionální.[3]
Teorie automatů
Formální definice řady a k-pravidelná sekvence vede k podobnosti automatu jako Schützenberger maticový stroj.[4][5]
Dějiny
Pojem k-pravidelné sekvence byly nejprve zkoumány v páru papírů Allouche a Shallit.[6] Před tím Berstel a Reutenauer studovali teorii racionální série, který úzce souvisí s k-pravidelné sekvence.[7]
Příklady
Posloupnost pravítek
Nechat být -adické ocenění z . Sekvence vládce (OEIS: A007814) je -pravidelné a -jádro
je obsažen v dvourozměrném vektorovém prostoru generovaném a konstantní posloupnost . Tyto základní prvky vedou k relacím opakování
které spolu s počátečními podmínkami a , jednoznačně určit posloupnost.[8]
Sekvence Thue – Morse
The Sekvence Thue – Morse t(n) (OEIS: A010060) je pevný bod morfismu 0 → 01, 1 → 10. Je známo, že sekvence Thue – Morse je 2-automatická. Je tedy také 2-regulární a jeho 2-jádro
sestává z subsekcí a .
Cantorova čísla
Posloupnost Cantorova čísla C(n) (OEIS: A005823) se skládá z čísel, jejichž trojice expanze neobsahují žádné 1 s. Je jednoduché to ukázat
a proto je posloupnost Cantorových čísel 2 pravidelná. Podobně Stanleyova sekvence
čísel, jejichž ternární expanze neobsahují 2s, je také 2-regulární.[9]
Řazení čísel
Trochu zajímavá aplikace pojmu k-pravidelnost širšího studia algoritmů se nachází v analýze Sloučit třídění algoritmus. Vzhledem k seznamu n hodnoty, počet srovnání provedených algoritmem řazení sloučení je třídění čísel, řídí se relací opakování
Ve výsledku posloupnost definovaná relací opakování pro sloučení, T(n), představuje 2-pravidelnou sekvenci.[10]
Další sekvence
Li je celočíselný polynom, pak je k-pravidelné pro každého .
The Glaisher - Gould sekvence je 2-pravidelná. Sekvence Stern – Brocot je 2-pravidelná.
Allouche a Shallit uvádějí řadu dalších příkladů k-pravidelné sekvence v jejich dokumentech.[6]
Vlastnosti
k-pravidelné sekvence vykazují řadu zajímavých vlastností.
- Každý k-automatická sekvence je k-pravidelný.[11]
- Každý k-synchronizovaná sekvence je k-pravidelný.
- A k-pravidelná sekvence nabývá konečně mnoha hodnot, právě když je k-automatický.[12] To je okamžitý důsledek třídy k-pravidelné sekvence jako zobecnění třídy k-automatické sekvence.
- Třída k-pravidelné sekvence jsou uzavřeny pod termwise sčítáním, termwise multiplikací a konvoluce. Třída k-pravidelné sekvence jsou také uzavřeny při změně měřítka každého členu sekvence o celé číslo λ.[12][13][14][15] Zejména soubor k-pravidelná výkonová řada tvoří kruh.[16]
- Li je k-pravidelné, pak pro všechna celá čísla , je k-automatický. Konverzace však neplatí.[17]
- Pro multiplikativně nezávislé k, l ≥ 2, pokud je sekvence obojí k-pravidelné a l-pravidelné, pak sekvence splňuje lineární opakování.[18] Toto je zevšeobecnění výsledku kvůli Cobhamovi, pokud jde o sekvence, které jsou obě k-automatické a l-automatický.[19]
- The nth termín k-pravidelná sekvence celých čísel roste nanejvýš polynomiálně v n.[20]
- Li je pole a , pak posloupnost sil je k-pravidelné právě tehdy nebo je kořenem jednoty.[21]
Prokazování a vyvracení k-pravidelnost
Byla dána kandidátní sekvence o kterém se neví k-pravidelný, k-regularity lze obvykle prokázat přímo z definice výpočtem prvků jádra a dokazovat, že všechny prvky formuláře s dostatečně velký a lze psát jako lineární kombinace prvků jádra s menšími exponenty místo . To je obvykle výpočetně jednoduché.
Na druhou stranu vyvracení k-pravidelnost kandidátské sekvence obvykle vyžaduje jeden k výrobě a - lineárně nezávislá podmnožina v jádře , což je obvykle složitější. Zde je jeden příklad takového důkazu.
Nechat označte počet je v binární expanzi . Nechat označte počet je v binární expanzi . Sekvence lze ukázat jako 2-pravidelné. Sekvence následující argument však není pravidelný 2. Předpokládat je 2-pravidelný. Tvrdíme, že prvky pro a 2-jádra jsou lineárně nezávislé . Funkce je surjective na celá čísla, tak ať být nejméně celé číslo takové, že . Podle 2 pravidelnosti , existují a konstanty takové, že pro každého ,
Nechat být nejmenší hodnotou, pro kterou . Pak pro každého ,
Vyhodnocování tohoto výrazu na , kde a tak dále za sebou získáváme na levé straně
a na pravé straně,
Z toho vyplývá, že pro každé celé číslo ,
Ale pro , pravá strana rovnice je monotónní, protože má tvar pro některé konstanty , zatímco levá strana není, jak lze zkontrolovat postupným připojením , , a . Proto, není 2-pravidelné.[22]
Poznámky
- ^ Allouche a Shallit (1992), definice 2.1.
- ^ A b Allouche & Shallit (1992), věta 2.2.
- ^ Allouche & Shallit (1992), Theorem 4.3.
- ^ Allouche & Shallit (1992), věta 4.4.
- ^ Schützenberger, M.-P. (1961), „K definici rodiny automatů“, Informace a kontrola, 4 (2–3): 245–270, doi:10.1016 / S0019-9958 (61) 80020-X.
- ^ A b Allouche & Shallit (1992, 2003).
- ^ Berstel, Jean; Reutenauer, Christophe (1988). Racionální série a jejich jazyky. Monografie EATCS o teoretické informatice. 12. Springer-Verlag. ISBN 978-3-642-73237-9.
- ^ Allouche & Shallit (1992), příklad 8.
- ^ Allouche & Shallit (1992), příklady 3 a 26.
- ^ Allouche & Shallit (1992), příklad 28.
- ^ Allouche & Shallit (1992), Theorem 2.3.
- ^ A b Allouche & Shallit (2003), str. 441.
- ^ Allouche & Shallit (1992), Theorem 2.5.
- ^ Allouche a Shallit (1992), Věta 3.1.
- ^ Allouche & Shallit (2003), str. 445.
- ^ Allouche a Shallit (2003), str. 446.
- ^ Allouche a Shallit (2003), str. 441.
- ^ Bell, J. (2006). "Zobecnění Cobhamovy věty pro pravidelné sekvence". Seminář Lotharingien de Combinatoire. 54A.
- ^ Cobham, A. (1969). "Na základní závislosti množin čísel rozpoznatelných konečnými automaty". Matematika. Teorie systémů. 3 (2): 186–192. doi:10.1007 / BF01746527.
- ^ Allouche & Shallit (1992) Věta 2.10.
- ^ Allouche a Shallit (2003), str. 444.
- ^ Allouche a Shallit (1993), str. 168–169.
Reference
- Allouche, Jean-Paul; Shallit, Jeffrey (1992), „The ring of k-pravidelné sekvence ", Teoretická. Comput. Sci., 98 (2): 163–197, doi:10.1016 / 0304-3975 (92) 90001-v.
- Allouche, Jean-Paul; Shallit, Jeffrey (2003), „The ring of k-pravidelné sekvence, II ", Teoretická. Comput. Sci., 307: 3–29, doi:10.1016 / s0304-3975 (03) 00090-2.
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatické sekvence: Teorie, Aplikace, Zobecnění. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.