Lyndonské slovo - Lyndon word - Wikipedia

v matematika v oblastech kombinatorika a počítačová věda, a Slovo Lyndon je neprázdné tětiva to je přísně menší lexikografický řád než všechny jeho rotace. Lyndonská slova jsou pojmenována po matematikovi Roger Lyndon, který je vyšetřoval v roce 1954 a zavolal jim standardní lexikografické sekvence.[1] Anatoly Shirshov představil Lyndonova slova v roce 1953 a nazval je běžná slova.[2] Lyndonova slova jsou zvláštním případem Hall slova; téměř všechny vlastnosti lyndonských slov sdílí Hallova slova.

Definice

Existuje několik ekvivalentních definic.

A k- dlouhé lyndonské slovo délky n > 0 je n-charakter tětiva přes abeceda velikosti k, a který je jedinečným minimálním prvkem v lexikografické objednávání v multiset všech jeho rotací. Být mimořádně nejmenší rotací znamená, že lyndonské slovo se liší od kterékoli ze svých netriviálních rotací, a je tedy neperiodické.[3]

Alternativně slovo w je lyndonské slovo právě tehdy, pokud je neprázdné a lexikograficky přísně menší než kterákoli z jeho správných přípon, to znamená w < proti pro všechna neprázdná slova proti takhle w = uv a u je neprázdné.

Další charakteristika je následující: Lyndonské slovo má tu vlastnost, že je neprázdné a kdykoli je rozděleno na dva neprázdné podřetězce, levý podřetězec je vždy lexikograficky menší než pravý podřetězec. To je, pokud w je lyndonské slovo a w = uv je libovolná faktorizace na dva podřetězce, s u a proti chápáno jako neprázdné u < proti. Tato definice znamená, že řetězec w of length ≥ 2 is a Lyndon word if and only if there exist Lyndon words u a proti takhle u < proti a w = uv.[4] I když může existovat více než jedna možnost u a proti s touto vlastností existuje zvláštní volba, která se nazývá standardní faktorizace, ve kterém proti je co nejdéle.[5]

Výčet

Lyndonská slova nad binární abecedou se dvěma symboly {0,1}, seřazená podle délky a poté lexikograficky v každé třídě délky, tvoří nekonečnou sekvenci, která začíná

0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ...

První řetězec, který do této sekvence nepatří, „00“, je vynechán, protože je periodický (skládá se ze dvou opakování podřetězce „0“); druhý vynechaný řetězec „10“ je neperiodický, ale ve své třídě permutace není minimální, protože jej lze cyklicky permutovat na menší řetězec „01“.

Prázdný řetězec také splňuje definici lyndonského slova o délce nula. Počet binárních lyndonských slov každé délky, počínaje nulovou délkou, tvoří celočíselná sekvence

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (sekvence A001037 v OEIS )

Lyndonská slova odpovídají neperiodickým náhrdelník zástupci tříd a lze s nimi tedy počítat Moreauova funkce počítání náhrdelníků.[3][6]

Generace

Duval (1988) poskytuje efektivní algoritmus za uvedení maximálně dlouhých lyndonských slov n s danou velikostí abecedy s v lexikografický řád. Li w je jedno ze slov v pořadí, poté další slovo za w lze najít pomocí následujících kroků:

  1. Opakujte symboly z w vytvořit nové slovo X přesně n, Kde ith symbol X je stejný jako symbol na pozici (i délka módu (w)) z w.
  2. Pokud je konečný symbol X je poslední symbol v seřazeném abecedním pořadí, odstraňte jej a vytvořte kratší slovo.
  3. Vyměňte poslední zbývající symbol X jeho nástupce v seřazeném pořadí abecedy.

Nejhorší doba pro generování nástupce slova w tímto postupem je O (nPokud jsou však generovaná slova uložena v pole délky na výstavba X z w se provádí přidáním symbolů na konec w spíše než vytvořením nové kopie souboru w, pak průměrná doba generování nástupce w (za předpokladu, že každé slovo je stejně pravděpodobné) je konstantní. Proto sekvence všech délkových slov Lyndonu n lze generovat v čase úměrném délce sekvence.[7] Konstantní zlomek slov v této sekvenci má přesnou délku n, takže stejný postup lze použít k efektivnímu generování slov délky přesně n nebo slova, jejichž délka se dělí nfiltrováním vygenerovaných slov, která těmto kritériím neodpovídají.

Standardní faktorizace

Podle Věta Chen – Fox – Lyndon, každý řetězec může být vytvořen jedinečným způsobem zřetězením sekvence lyndonských slov takovým způsobem, že slova v sekvenci se nezvyšují lexikograficky.[8] Konečné slovo Lyndon v této sekvenci je lexikograficky nejmenší přípona daného řetězce.[9] Faktorizaci do nezvyšující se sekvence lyndonských slov (tzv. Lyndonská faktorizace) lze postavit v lineární čas.[9] Lyndonovy faktorizace mohou být použity jako součást bijektivní varianty Burrows – Wheelerova transformace pro komprese dat,[10] a v algoritmech pro digitální geometrie.[11]

Takové faktorizace lze zapsat (jednoznačně) jako konečné binární stromy s listy označenými abecedou, přičemž každá pravá větev je dána posledním Lyndonovým slovem v pořadí.[12] Takovým stromům se někdy říká standardní držáky a lze jej brát jako faktorizaci prvků a volná skupina nebo jako základní prvky pro a zdarma Lie algebra. Tyto stromy jsou zvláštním případem Hall stromy (protože Lyndonova slova jsou zvláštním případem Hallových slov), a tak podobně Hallova slova poskytují standardní řád, který se nazývá proces sběru komutátoru pro skupiny a základ pro Lieovy algebry.[13][14][15]Ve skutečnosti poskytují výslovnou konstrukci pro komutátory, kteří se objevují v Poincaré – Birkhoff – Wittova věta potřebné pro stavbu univerzální obklopující algebry.

Každé slovo Lyndon lze chápat jako permutace, přípona standardní permutace.

Duvalův algoritmus

Duval (1983) vyvinul algoritmus pro nalezení standardní faktorizace, která běží v lineárním čase a konstantním prostoru. Iteruje přes řetězec a pokouší se najít co nejdelší lyndonské slovo. Když ji najde, přidá ji do seznamu výsledků a pokračuje v hledání zbývající části řetězce. Výsledný seznam řetězců je standardní faktorizace daného řetězce. Následuje formálnější popis algoritmu.

Daný řetězec S délky N, měli byste pokračovat v následujících krocích:

  1. Nechat m být indexem kandidáta na symbol, který má být připojen k již shromážděným symbolům. Zpočátku, m = 1 (indexy symbolů v řetězci začínají od nuly).
  2. Nechat k být indexem symbolu, s nímž bychom srovnávali ostatní. Zpočátku, k = 0.
  3. Zatímco k a m jsou menší než N, porovnat S [k] (dále jen k-tý symbol řetězce S) až S [m]. Existují tři možné výsledky:
    1. S [k] je rovný S [m]: připojit S [m] k aktuálním shromážděným symbolům. Přírůstek k a m.
    2. S [k] je méně než S [m]: pokud připojíme S [m] k aktuálním shromážděným symbolům dostaneme slovo Lyndon. Ale zatím jej nemůžeme přidat do seznamu výsledků, protože to může být jen část většího lyndonského slova. Tedy jen přírůstek m a nastavit k na 0, takže další symbol bude porovnán s prvním v řetězci.
    3. S [k] je větší než S [m]: pokud připojíme S [m] k aktuálním shromážděným symbolům to nebude ani lyndonské slovo, ani možný začátek jednoho. Přidejte tedy první m-k shromážděné symboly do seznamu výsledků, odstranit je z řetězce, nastavit m na 1 a k na 0, aby ukazovaly na druhý a první symbol řetězce.
  4. Když m> N, je to v podstatě to samé jako narazit na mínus nekonečno, tedy přidat první m-k shromážděné symboly do seznamu výsledků po jejich odstranění z řetězce, nastavit m na 1 a k na 0 a vrátit se k předchozímu kroku.
  5. Přidat S do seznamu výsledků.

Spojení s de Bruijn sekvencemi

Pokud jeden zřetězí společně, v lexikografickém pořadí, všechna lyndonská slova, která mají délku dělící dané číslo n, výsledkem je a de Bruijnova sekvence, kruhová posloupnost symbolů, takže každý možnýn posloupnost se objeví právě jednou jako jedna z jejích sousedících podsekvencí. Například zřetězení binárních Lyndonových slov, jejichž délka dělí čtyři, je

0 0001 0011 01 0111 1

Tato konstrukce spolu s účinným generováním lyndonských slov poskytuje efektivní metodu pro konstrukci konkrétní de Bruijn sekvence v lineární čas a logaritmický prostor.[16]

Další vlastnosti a aplikace

Lyndonská slova mají aplikaci na popis zdarma Lie algebry při vytváření základu pro homogenní část daného stupně; to byla Lyndonova původní motivace k zavedení těchto slov.[4] Lyndonská slova lze chápat jako zvláštní případ Hala sady.[4]

Pro nejlepší p, počet neredukovatelných monické polynomy stupně d přes pole je stejný jako počet lyndonských slov délky d v abecedě p symboly; mohou být umístěny do explicitní korespondence.[17]

Radfordova věta uvádí, že a náhodné algebry nad polem charakteristiky 0 lze zobrazit jako polynomiální algebru nad Lyndonovými slovy. Přesněji řečeno A být abeceda, ať k být polem charakteristiky 0 (nebo obecněji komutativní ℚ-algebra) a nechat R být zdarma nekomutativní k-algebra k ⟨ XA | A ∈ A ⟩. Slova skončila A pak lze identifikovat pomocí "nekomutativních monomiálů" (tj. produktů z XA) v R; jmenovitě identifikujeme slovo (A1,A2,...,An) s monomií XA1XA2...XAn. Slova tedy skončila A tvoří a k-vektorový vesmírný základ R. Pak zamíchat produkt je definováno na R; toto je k-bilineární, asociativní a komutativní produkt, který je označen ш a který na slovech lze rekurzivně definovat

1 ш proti = proti pro jakékoli slovo proti;
u ш 1 = u pro jakékoli slovo u;
ua ш vb = (u ш vb)A + (ua ш proti)b pro všechny A,b ∈ A a jakákoli slova u a proti.

The zamíchat algebru na abecedě A je definována jako skupina aditiv R obdařen ш jako násobení. Radfordova věta[18] nyní uvádí, že lyndonská slova jsou algebraicky nezávislé prvky této míchané algebry a generují ji; tedy algebra míchání je isomorfní s polynomiálním prstencem k, přičemž neurčité osoby odpovídají lyndonským slovům.[18]

Viz také

Poznámky

  1. ^ Lyndon (1954).
  2. ^ Shirshov (1953).
  3. ^ A b Berstel & Perrin (2007); Melançon (2001).
  4. ^ A b C Melançon (2001).
  5. ^ Berstel & Perrin (2007).
  6. ^ Ruskey (2003) poskytuje podrobnosti o těchto počtech slov Lyndon a několik souvisejících konceptů.
  7. ^ Berstel & Pocchiola (1994).
  8. ^ Melançon (2001). Berstel & Perrin (2007) napište, že i když se to obvykle připisuje Chen, Fox & Lyndon (1958), a vyplývá z výsledků tohoto článku, bylo to výslovně uvedeno až Schützenberger (1965). Bylo to výslovně formulováno Shirshov (1958) viz Schützenberger & Sherman (1963).
  9. ^ A b Duval (1983).
  10. ^ Gil & Scott (2009); Kufleitner (2009).
  11. ^ Brlek a kol. (2009).
  12. ^ Amy Glen, “Kombinatorika lyndonských slov " (2012)
  13. ^ Guy Melançon, (1992) "Kombinatorika Hallových stromů a Hallových slov ", Journal of Combinatoric Theory, 59A(2), str. 285–308.
  14. ^ Guy Melançon a Christophe Reutenauer (1989), „Lyndonova slova, algebry a shuffle zdarma“, Kanadský žurnál matematiky. 41, Č. 4, str. 577-591.
  15. ^ Christophe Hohlweg a Christophe Reutenauer, “Lyndonská slova, obměny a stromy ", (2003) LaCIM
  16. ^ Podle Berstel & Perrin (2007), sekvence generovaná tímto způsobem byla poprvé popsána (jinou metodou generování) pomocí Martin (1934) a souvislost mezi ním a Lyndonovými slovy byla pozorována Fredricksen & Maiorana (1978).
  17. ^ Solomon W. Golomb (1969) „Neredukovatelné polynomy, synchronizační kódy, primitivní náhrdelníky a cyklotomická algebra“, Proc. Conf Combinatorial Mathematics and its Applications, str. 358--370 (University of North Carolina).
  18. ^ A b Radford (1979)

Reference