Бициклическая полугруппа
В математике бициклическая полугруппа — алгебраический объект, важный для структурной теории полугрупп . Хотя на самом деле это моноид , его обычно называют просто полугруппой. Возможно, его легче всего понять как синтаксический моноид , описывающий язык Дайка сбалансированных пар скобок. Таким образом, он находит общие применения в комбинаторике , например, для описания бинарных деревьев и ассоциативных алгебр .
Первое опубликованное описание этого объекта было дано Евгением Ляпиным в 1953 году. Альфред Х. Клиффорд и Гордон Престон утверждают, что один из них, работая с Дэвидом Рисом , обнаружил его независимо (без публикации) в какой-то момент до 1943 года.
Существует по крайней мере три стандартных способа построения бициклической полугруппы и различные обозначения для обозначения ее. Ляпин назвал его П ; Клиффорд и Престон использовали ; и самые последние статьи, как правило, используют B . В этой статье будет использован современный стиль.
Бициклическая полугруппа — это свободный моноид на двух образующих p и q при соотношении p q = 1. То есть каждый элемент полугруппы представляет собой строку из этих двух букв при условии, что подпоследовательность « p q » не появляется. Полугрупповая операция — это конкатенация строк, которая явно ассоциативна . Затем можно показать, что все элементы B на самом деле имеют форму q a p b для некоторых натуральных чисел a и b . Операция композиции упрощается до
Способ ограничения этих показателей предполагает, что « структуру p и q » можно отбросить, оставив только операции над частью « a и b ». Итак , B — полугруппа пар натуральных чисел (включая ноль) с операцией [1]
Этого достаточно, чтобы определить B так, чтобы это был тот же объект, что и в исходной конструкции. Точно так же, как p и q изначально генерировали B с пустой строкой в качестве моноида, эта новая конструкция B имеет генераторы (1, 0) и (0, 1) с единицей (0, 0).