Лемма Леви

Случай uw =  x  и v =  wy леммы Леви

В теоретической информатике и математике , особенно в области комбинаторики слов , лемма Леви утверждает, что для всех строк u , v , x и y , если uv  =  xy , то существует строка w такая, что либо

uw = x и v  =  wy (если | u | ≤ | x |)

или

u  =  xw и wv  =  y (если | u | ≥ | x |)

То есть, есть строка w, которая находится "посередине", и может быть сгруппирована с одной или другой стороны. Лемма Леви названа в честь Фридриха Вильгельма Леви , который опубликовал ее в 1944 году. ^[1]

Приложения

Лемму Леви можно применять многократно для решения уравнений в словах ; в этом контексте ее иногда называют преобразованием Нильсена по аналогии с преобразованием Нильсена для групп . Например, начав с уравнения xα = yβ , где x и y — неизвестные, мы можем преобразовать его (предполагая, что |x| ≥ |y| , поэтому существует t, такое что x = yt ) в ytα = yβ , то есть в tα = β . Этот подход приводит к графу подстановок, сгенерированному путем многократного применения леммы Леви. Если каждое неизвестное появляется не более двух раз, то уравнение в словах называется квадратным; в квадратном уравнении в словах граф, полученный путем многократного применения леммы Леви, конечен, поэтому он разрешим, если квадратное уравнение в словах имеет решение . ^[2] Более общим методом решения уравнений в словах является алгоритм Маканина. ^{[3] [4]}

Обобщения

Вышеизложенное известно как лемма Леви для строк ; лемма может встречаться в более общей форме в теории графов и в теории моноидов ; например, существует более общая лемма Леви для следов, первоначально предложенная Кристин Дюбок. ^[5] Несколько доказательств леммы Леви для следов можно найти в Книге следов . ^[6]

Говорят, что моноид, в котором лемма Леви верна, обладает свойством равноделимости . ^[7] Свободный моноид строк и конкатенации строк обладает этим свойством (по лемме Леви для строк), но сама по себе равноделимость недостаточна для гарантии того, что моноид свободен. Однако равноделимый моноид M свободен, если дополнительно существует гомоморфизм f из M в моноид натуральных чисел (свободный моноид с одной образующей) со свойством, что прообраз 0 содержит только единичный элемент M , т. е . . (Заметим, что f просто будучи гомоморфизмом, не гарантирует это последнее свойство, поскольку может быть несколько элементов M, отображенных в 0.) ^[8] Моноид, для которого существует такой гомоморфизм, также называется градуированным (а f называется градацией). ^[9] ${\displaystyle f^{-1}(0)=\{1_{M}\}}$

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

• Операции со строками
• Строковые функции (программирование)

Примечания

1. Леви, Ф. В. (1944), «О полугруппах», Бюллетень Калькуттского математического общества , 36 : 141–146, MR  0011694, Zbl  0061.02405.
2. Матиясевич, Ю. В. (1968), "Связь между системами слов и уравнений длины и десятой проблемой Гильберта", Зап. Научн. Сем. Ленинград. Отдел. Мат. Инст. Стеклов. (ЛОМИ) , 8 : 132–144.
3. Маканин, ГС (1977), "Проблема разрешимости уравнений в свободной полугруппе", Матем. сборник , 103 (2), английский перевод в Матем. сборник СССР 32 (1977): 147–236, Bibcode :1977SbMat..32..129M, doi :10.1070/SM1977v032n02ABEH002376
4. М. Лотер (2002). "12" . Алгебраическая комбинаторика слов . Cambridge University Press. ISBN 0-521-81220-8.
5. Дубок, Хр. (1986), «О некоторых уравнениях в свободных частично коммутативных моноидах», Теоретическая информатика , 46 : 159–174, doi : 10.1016/0304-3975(86)90028-9
6. Volker Diekert; Grzegorz Rozenberg , ред. (1995). Книга следов . World Scientific. стр. 1–576. ISBN 981-02-2058-8.
7. Альдо де Лука; Стефано Варриккио (1999). Конечность и регулярность в полугруппах и формальных языках . Springer Berlin Heidelberg. стр. 2. ISBN 978-3-642-64150-3.
8. М. Лотер (1997). Комбинаторика слов . Cambridge University Press. стр. 13. ISBN 978-0-521-59924-5.
9. Сакарович, Жак (2009), Элементы теории автоматов , Перевод с французского Рубена Томаса, Кембридж: Cambridge University Press , стр. 26, ISBN 978-0-521-84425-3