Содержание раздела:
Первостепенной алгоритмической задачей, связанной с косами, является их распознавание.
Определение. Задачей распознавания кос (или проблемой тождества в группе кос) называется алгоритмическая задача разрешимости, заключающаяся в определении того, представляют ли два заданных артиновских слова одинаковые косы.
Распознаванием кос впервые занимался К. Ф. Гаусс в 1815 году:
Черновик Гаусса, в котором он описал обобщения коэффициентов зацепления нитей косы
Оказывается, общая задача распознавания пар кос сводится к своему частному случаю.
Лемма. Задача распознавания кос равносильна задаче определения того, представляет ли заданное артиновское слово тривиальную косу.
Доказательство. Имеем $x = y \ \ \Longleftrightarrow \ \ xy^{-1}=1.$
Запутанное изображение тривиальной косы
<aside> 💡 Инварианты кос предоставляют подход к решению задачи распознавания.
</aside>
На практике простейшие инварианты часто принимают одинаковые значения на разных косах, поэтому для решения задачи распознавания необходимы продвинутые методы.
На самом деле, задача распознавания кос алгоритмически разрешима, и известно несколько существенно различных таких алгоритмов, каждый из которых позволяет взглянуть на косы с совершенно новой точки зрения. Их можно в основном разделить на две категории: алгебраические и геометрические.
К категории алгебраических решений относится обнаружение той или иной однозначной записи кос. Такие записи называются нормальными формами.
<aside> 💡 Суть. Если в результате приведения двух кос к их нормальным формам получились различные записи, то исходные косы обязательно различны.
</aside>
Точнее, как мы обсудили выше, достаточно научиться отличать косу от тривиальной, поэтому алгебраические решения задачи распознавания обычно предоставляют способ привести каждую косу либо к виду тривиальной косы, либо к тому, по которому нетривиальность ясна.
Определение. Непустая запись в образующих Артина называется положительной по Деорнуа, если образующая $\sigma_k^{\pm 1}$ с наименьшим индексом (среди присутствующих) входит только в положительных степенях. Коса называется положительной по Деорнуа, если она имеет положительную по Деорнуа запись.
