Monoidní faktorizace - Monoid factorisation

V matematice, a faktorizace a volný monoid je posloupnost podmnožin slov s vlastností, že každé slovo ve volném monoidu lze zapsat jako zřetězení prvků čerpaných z podmnožin. Věta Chen – Fox – Lyndon uvádí, že Lyndonova slova poskytnout faktorizaci. Schützenbergerova věta spojuje definici z hlediska multiplikativní vlastnosti s vlastností aditivní.^{[je zapotřebí objasnění ]}

Nechat A^* být volný monoid na abecedě A. Nechat X_i být posloupností podmnožin A^* indexováno a zcela objednané sada indexů Já. Faktorizace slova w v A^* je výraz

${ displaystyle w = x_ {i_ {1}} x_ {i_ {2}} cdots x_ {i_ {n}} }$

s ${ displaystyle x_ {i_ {j}} v X_ {i_ {j}}}$ a ${ displaystyle i_ {1} geq i_ {2} geq ldots geq i_ {n}}$. Někteří autoři mění pořadí nerovností.

Věta Chen – Fox – Lyndon

A Slovo Lyndon přes úplně uspořádanou abecedu A je slovo, které je lexikograficky méně než všechny jeho rotace.^[1] The Věta Chen – Fox – Lyndon uvádí, že každý řetězec může být vytvořen jedinečným způsobem zřetězením nerostoucí sekvence Lyndonova slova. Proto brát X_l být singletonovou sadou {l} pro každé slovo Lyndon l, s nastaveným indexem L slov Lyndona seřazených lexikograficky získáme faktorizaci A^*.^[2] Takovou faktorizaci lze nalézt v lineárním čase.^[3]

Hall slova

The Hall set poskytuje faktorizaci.^[4]Ve skutečnosti jsou lyndonská slova zvláštním případem Hallových slov. Článek o Hall slova poskytuje náčrt všech mechanismů potřebných k prokázání této faktorizace.

Bisection

A půlení volného monoidu je faktorizace s pouhými dvěma třídami X₀, X₁.^[5]

Příklady:

A = {A,b}, X₀ = {A^*b}, X₁ = {A}.

Li X, Y jsou disjunktní sady neprázdných slov, pak (X,Y) je půlící část A* jen a jen pokud^[6]

${ displaystyle YX cup A = X cup Y .}$

V důsledku toho pro jakýkoli oddíl P , Q z A⁺ existuje jedinečná půlení (X,Y) s X podmnožina P a Y podmnožina Q.^[7]

Schützenbergerova věta

Tato věta říká, že sekvence X_i podskupin A^* tvoří faktorizaci právě tehdy, pokud platí dva z následujících tří příkazů:

• Každý prvek A^* má alespoň jeden výraz v požadované formě;^{[je zapotřebí objasnění ]}
• Každý prvek A^* má nejvýše jeden výraz v požadované formě;
• Každá třída konjugátu C splňuje pouze jeden z monoidů M_i = X_i* a prvky C v M_i jsou konjugovány v M_i.^{[8][je zapotřebí objasnění ]}

Viz také

• Sesquipower

Reference

• Lothaire, M. (1997), Kombinatorika slovEncyklopedie matematiky a její aplikace 17, Perrin, D .; Reutenauer, C .; Berstel, J .; Pin, J. E .; Pirillo, G .; Foata, D .; Sakarovitch, J .; Simon, I .; Schützenberger, M. P .; Choffrut, C .; Cori, R .; Lyndon, Roger; Rota, Gian-Carlo. Předmluva Rogera Lyndona (2. vyd.), Cambridge University Press, ISBN  0-521-59924-5, Zbl  0874.20040