Факторизация моноида - Monoid factorisation

В математике факторизация из свободный моноид представляет собой последовательность подмножеств слов со свойством, что каждое слово в свободном моноиде может быть записано как конкатенация элементов, взятых из подмножеств. Теорема Чена – Фокса – Линдона утверждает, что Слова Линдона предоставить факторизацию. Теорема Шютценбергера связывает определение в терминах мультипликативного свойства с аддитивным свойством.^{[требуется разъяснение ]}

Позволять А^* быть свободный моноид по алфавиту А. Позволять Икс_я последовательность подмножеств А^* проиндексировано полностью заказанный набор индексов я. Факторизация слова ш в А^* это выражение

{ Displaystyle ш = х_ {я_ {1}} х_ {я_ {2}} cdots х_ {я_ {п}} }

с ${ displaystyle x_ {i_ {j}} in X_ {i_ {j}}}$ и ${ Displaystyle i_ {1} geq i_ {2} geq ldots geq i_ {п}}$ . Некоторые авторы меняют порядок неравенств.

Теорема Чена – Фокса – Линдона.

А Линдон слово над полностью упорядоченным алфавитом А это слово, которое лексикографически меньше, чем все его вращения.^[1] В Теорема Чена – Фокса – Линдона. утверждает, что каждая строка может быть сформирована уникальным образом путем объединения невозрастающей последовательности Слова Линдона. Следовательно, принимая Икс_л быть одноэлементным набором {л} для каждого слова Линдона л, с набором индексов L слов Линдона, упорядоченных лексикографически, мы получаем факторизацию А^*.^[2] Такую факторизацию можно найти за линейное время.^[3]

Слова зала

В Набор для прихожей обеспечивает факторизацию.^[4]Действительно, слова Линдона являются частным случаем холловских слов. Статья о Слова зала дает набросок всех механизмов, необходимых для доказательства этой факторизации.

Пополам

А деление пополам свободного моноида представляет собой факторизацию всего с двумя классами Икс₀, Икс₁.^[5]

Примеры:

А = {а,б}, Икс₀ = {а^*б}, Икс₁ = {а}.

Если Икс, Y - непересекающиеся множества непустых слов, то (Икс,Y) является делением пополам А* если и только если^[6]

{ Displaystyle YX чашка A = X чашка Y .}

Как следствие, для любого раздела п , Q из А⁺ есть единственное деление пополам (Икс,Y) с Икс подмножество п и Y подмножество Q.^[7]

Теорема Шютценбергера

Эта теорема утверждает, что последовательность Икс_я подмножеств А^* образует факторизацию тогда и только тогда, когда выполняются два из следующих трех утверждений:

Каждый элемент А^* имеет хотя бы одно выражение в требуемой форме;^{[требуется разъяснение ]}
Каждый элемент А^* имеет не более одного выражения в требуемой форме;
Каждый сопряженный класс C встречается только с одним из моноидов M_я = Икс_я* и элементы C в M_я сопряжены в M_я.^[8]^{[требуется разъяснение ]}

Смотрите также

Sesquipower