16
правок
Изменения
Определяющие соотношения
# Пар, пересекающихся по одной позиции. Имеем <math>L_1 a L_2 \rightarrow L_1 a a^{-1} a L_2 \rightarrow L_1 a L_2</math>, и в этом случае мы также можем избавиться от <math>S_{i}</math> и <math>S_{i + 1}</math>, что также уменьшит итоговую сумму длин строк.
Таким образом, мы пришли к противоречию во всех случаях, а это значит, что мы доказали теорему.
}}
== Задание группы определяющими соотношениями ==
Пусть также имеем алфавит <math>\Sigma = \{ a_1, \dots a_n \} </math> и набор пар строк <math>S_1 \sim \omega_1, \dots, S_n \sim \omega_n</math>. Разрешается где угодно менять <math>\omega_i</math> на <math>S_i</math> и наоборот.
{{Определение
|definition=
Выражения <math>S_1 \sim \omega_1, \dots, S_n \sim \omega_n</math> называются '''определяющими соотношениями'''.
}}
{{Утверждение
|about=без доказательства
|statement=
Задача проверки эквивалентности строк при заданных определяющих соотношениях алгоритмически неразрешима.
}}
[[Категория:Теория групп]]
