Моноидная факторизация

В математике факторизация это — свободного моноида последовательность подмножеств слов, обладающая тем свойством, что каждое слово в свободном моноиде может быть записано как конкатенация элементов, взятых из подмножеств. Теорема Чена- Фокса - Линдона утверждает, что слова Линдона обеспечивают факторизацию. Теорема Шютценбергера связывает определение в терминах мультипликативного свойства с аддитивным свойством.

Пусть А ^* быть свободным моноидом в алфавите A . Пусть X _i — последовательность подмножеств A ^* индексируется полностью упорядоченным индексов I. набором Факторизация слова w в A ^* это выражение

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

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

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

Слово Линдона в полностью упорядоченном алфавите A — это слово, которое лексикографически меньше всех его вращений. Теорема Чена-Фокса-Линдона утверждает, что каждая строка может быть сформирована уникальным способом путем объединения лексикографически невозрастающей последовательности слов Линдона. Следовательно, принимая X _l за одноэлементное множество { l } для каждого слова Линдона l с индексным набором L слов Линдона, упорядоченных лексикографически, мы получаем факторизацию A ^* . Такая факторизация может быть найдена в линейном времени и постоянном пространстве с помощью алгоритма Дюваля. Алгоритм в коде Python :

def chen_fox_lyndon_factorization(s: list[int]) -> list[int]:
    """Monoid factorisation using the Chen–Fox–Lyndon theorem.

    Args:
        s: a list of integers

    Returns:
        a list of integers
    """
    n = len(s)
    factorization = []
    i = 0
    while i < n:
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i
            else:
                k += 1
            j += 1
        while i <= k:
            factorization.append(s[i:i + j - k])
            i += j - k
    return factorization

Слова зала

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

деление пополам

Разделение свободного моноида пополам — это факторизация всего с двумя классами X ₀ , X ₁ .

Примеры:

А знак равно { а , б }, Икс ₀ = { а ^* б } ₁ = {a,

Если X , Y — непересекающиеся множества непустых слов, то ( X , Y ) — делимое пополам A * тогда и только тогда, когда

$YX\cup A=X\cup Y\ .$

Как следствие, для любого разбиения P , Q группы A ⁺ существует единственное деление пополам ( X , Y ), где X подмножество P , а Y — подмножество Q. —

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

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

• Каждый элемент А ^* имеет хотя бы одно выражение в требуемой форме;
• Каждый элемент А ^* имеет не более одного выражения в требуемой форме;
• Каждому сопряженному классу C соответствует только один из = X _и i * _, C в Mi сопряжены _Mi. в моноидов _Mi элементы

См. также

• Сесквипауэр

Ссылки

• Лотер, М. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, том. 17, Перрен, Д.; Ройтенауэр, К.; Берстель, Дж.; Пин, Ж.-Э. ; Пирилло, Г.; Фоата, Д.; Сакарович Дж.; Саймон, И.; Шютценбергер, член парламента; Шоффрут, К.; Кори, Р.; Линдон, Р.; Рота, Г.-К. Предисловие Роджера Линдона (2-е изд.), Cambridge University Press , ISBN  0-521-59924-5 , Збл   0874.20040