Faktoryzacja monoidów

W matematyce faktoryzacja wolnego monoidu to sekwencja podzbiorów słów z tą właściwością, że każde słowo w wolnym monoidzie można zapisać jako konkatenację elementów wylosowanych z podzbiorów . Twierdzenie Chen- Fox - Lyndona stwierdza, że słowa Lyndona dostarczają rozkładu na czynniki. Twierdzenie Schützenbergera wiąże definicję w kategoriach właściwości multiplikatywnej z właściwością addytywną . ^{[ wymagane wyjaśnienie ]}

Niech A ^* będzie wolnym monoidem na alfabecie A . Niech X _i będzie ciągiem podzbiorów A ^* indeksowanych przez całkowicie uporządkowany zbiór indeksów I . Faktoryzacja słowa w w A ^* jest wyrażeniem

{\ Displaystyle w = x_ {i_ {1}} x_ {i_ {2}} \ cdots x_ {i_ {n}} \}

z ${\ Displaystyle x_ {i_ {j}} \ w X_ {i_ {j}}}$ i ${\ Displaystyle i_ {1} \ geq i_ { 2}\geq \ldots \geq i_{n}}$ . Niektórzy autorzy odwracają kolejność nierówności.

Twierdzenie Chena – Foxa – Lyndona

Słowo Lyndona nad całkowicie uporządkowanym alfabetem A to słowo, które jest leksykograficznie mniejsze niż wszystkie jego rotacje. Twierdzenie Chen -Fox-Lyndon stwierdza, że każdy ciąg może być utworzony w unikalny sposób poprzez konkatenację nierosnącej sekwencji słów Lyndona. Stąd przyjmując, X _l jest pojedynczym zbiorem { l } dla każdego słowa Lyndona l , ze zbiorem indeksów L słów Lyndona uporządkowanych leksykograficznie, otrzymujemy faktoryzację A ^* . Taki rozkład na czynniki można znaleźć w czasie liniowym .

Słowa halowe

Zbiór Halla zapewnia rozkład na czynniki. Rzeczywiście, słowa Lyndona są szczególnym przypadkiem słów Halla. Artykuł na temat słów Halla zawiera szkic wszystkich mechanizmów potrzebnych do ustalenia dowodu tej faktoryzacji.

Przepołowienie

₀ Bisekcja swobodnego monoidu jest rozkładem na czynniki tylko z dwiema klasami X , X ₁ .

Przykłady:

₀ ZA = { za , b }, X = { za ^* b }, X ₁ = { za }.

Jeśli X , Y są rozłącznymi zbiorami niepustych słów, to ( X , Y ) jest dwusekcją A * wtedy i tylko wtedy, gdy

{\ Displaystyle YX \ kubek A = X \ kubek Y \ .}

W konsekwencji dla dowolnego podziału P , Q z A ⁺ istnieje unikalna bisekcja ( X , Y ) z X podzbiorem P i Y podzbiorem Q .

Twierdzenie Schützenbergera

Twierdzenie to stwierdza, że ciąg X _i podzbiorów zbioru A ^* tworzy rozkład na czynniki wtedy i tylko wtedy, gdy zachodzą dwa z następujących trzech stwierdzeń:

Każdy element A ^* ma co najmniej jedno wyrażenie w wymaganej postaci; ^{[ wymagane wyjaśnienie ]}
Każdy element A ^* ma co najwyżej jedno wyrażenie w wymaganej postaci;
Każda sprzężona klasa C spotyka tylko jedną z monoidów M _i = X _i *, a elementy C w M _i są sprzężone w M _i . ^{[ wymagane wyjaśnienie ]}

Zobacz też

Sesquipower

Lothaire, M. (1997), Kombinatoryka słów , Encyklopedia matematyki i jej zastosowań, tom. 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J.-É. ; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, poseł; Choffrut, C.; Cori, R.; Lyndon, R.; Rota, G.-C. Przedmowa Rogera Lyndona (wyd. 2), Cambridge University Press , ISBN 0-521-59924-5 , Zbl 0874.20040