Лемма Левиса - Levis lemma

В уф = Икс и v =wy случай леммы Леви

В теоретическая информатика и математика, особенно в районе комбинаторика слов, то Лемма Леви заявляет, что для всех струны ты, v, Икс и у, если УФ = ху, то существует строка ш так что либо

uw = x и v = wy (если |ты| ≤ |Икс|)

или же

ты = xw и wv = у (если |ты| ≥ |Икс|)

То есть есть строка ш то есть «посередине» и могут быть сгруппированы в одну или другую сторону. Лемма Леви названа в честь Фридрих Вильгельм Леви, опубликовавший его в 1944 году.[1]

Приложения

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

Обобщения

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

Говорят, что моноид, в котором выполняется лемма Леви, имеет свойство равноделимости.[7] В свободный моноид строк и конкатенация строк имеет это свойство (по лемме Леви для строк), но самой по себе равноделимости недостаточно, чтобы гарантировать, что моноид свободен. Однако равнораздельный моноид M бесплатно, если дополнительно существует гомоморфизм ж из M к моноид натуральных чисел (свободный моноид на одном образующем) со свойством прообраз 0 содержит только единичный элемент M, т.е. . (Обратите внимание, что ж просто быть гомоморфизмом не гарантирует это последнее свойство, так как может быть несколько элементов M сопоставлен с 0.)[8] Моноид, для которого существует такой гомоморфизм, также называется оцененный (и ж называется градацией).[9]

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

Примечания

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