В математике, факторизация из свободного моноиде представляет собой последовательность подмножеств слов со свойством , что каждое слово в свободном моноиде может быть записаны в виде конкатенации элементов , взятых из подмножеств. Теорема Чена – Фокса – Линдона утверждает, что слова Линдона обеспечивают факторизацию. Теорема Шютценбергера связывает определение в терминах мультипликативного свойства с аддитивным свойством. [ требуется разъяснение ]
Пусть * быть свободным Моноид на алфавите A . Пусть X я последовательность подмножеств A * индексируются по упорядоченному множеству индексов I . Факторизация слова w в A * - это выражение
с участием а также . Некоторые авторы меняют порядок неравенств.
Теорема Чена – Фокса – Линдона.
Линдон слово над упорядоченным алфавите А это слово , которое является лексикографически меньше всех его вращений. [1] Теорема Чена – Фокса – Линдона утверждает, что каждая строка может быть сформирована уникальным способом путем объединения невозрастающей последовательности слов Линдона . Следовательно, взяв X l как одноэлементное множество { l } для каждого слова Линдона l с индексным множеством L слов Линдона, упорядоченным лексикографически, мы получаем факторизацию A * . [2] Такую факторизацию можно найти за линейное время. [3]
Слова зала
Набор Холла обеспечивает факторизацию. [4] Действительно, слова Линдона являются частным случаем холловских слов. В статье о словах Холла дается набросок всех механизмов, необходимых для доказательства этой факторизации.
Деление пополам
Бисекция свободного моноида является факторизацией только с двумя классами X 0 , X 1 . [5]
Примеры:
- A = { a , b }, X 0 = { a * b }, X 1 = { a }.
Если X , Y - непересекающиеся множества непустых слов, то ( X , Y ) делится пополам A * тогда и только тогда, когда [6]
Как следствие, для любого разбиения P , Q из А + существует единственное бисекция ( Х , Y ) с X подмножество Р и Y подмножество Q . [7]
Теорема Шютценбергера
Эта теорема утверждает, что последовательность X i подмножеств A * образует факторизацию тогда и только тогда, когда выполняются два из следующих трех утверждений:
- Каждый элемент A * имеет хотя бы одно выражение в требуемой форме; [ требуется разъяснение ]
- Каждый элемент A * имеет не более одного выражения в требуемой форме;
- Каждый сопряженный класс C соответствует только одному из моноидов M i = X i *, а элементы C в M i сопряжены в M i . [8] [ требуется пояснение ]
Смотрите также
Рекомендации
- ^ Lothaire (1997) стр.64
- ^ Lothaire (1997) стр.67
- ^ Дюваль, Жан-Пьер (1983). «Факторизация слов по упорядоченному алфавиту». Журнал алгоритмов . 4 (4): 363–381. DOI : 10.1016 / 0196-6774 (83) 90017-2 ..
- ^ Гай Мелансон, (1992) « Комбинаторика деревьев Холла и слов Холла », Журнал комбинаторной теории , 59A (2), стр. 285–308.
- ^ Lothaire (1997) стр.68
- ^ Lothaire (1997) с.69
- ^ Lothaire (1997) стр.71
- ^ Lothaire (1997) стр.92
- Lothaire, M. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, 17 , Perrin, D .; Reutenauer, C .; Berstel, J .; Пин, JE; Pirillo, G .; Foata, D .; Сакарович, Дж .; Саймон, I .; Шютценбергер, депутат; Choffrut, C .; Cori, R .; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.), Cambridge University Press , ISBN 0-521-59924-5, Zbl 0874,20040