Введение

Идемпотентный полукольцо, наделенное оператором замыкания — алгебра Клине с операцией замыкания, являющаяся обобщением регулярных выражений.

В математике, алгебра Клине (произносится /ˈkliːni/ KLAYnee; названа в честь Стивена Коула Клине) — это идемпотентное (и, следовательно, частично упорядоченное) полукольцо, наделенное оператором замыкания. Она обобщает операции, известные из регулярных выражений.

История

Клейне ввёл регулярные выражения и сформулировал некоторые их алгебраические законы. Хотя он и не определил алгебры Клине, он поставил вопрос о существовании процедуры решения задачи эквивалентности регулярных выражений. Редко доказал, что никакое конечное множество уравнительных аксиом не может полностью характеризовать алгебру регулярных языков. Саломаа предложил полные аксиоматизации этой алгебры, однако зависящие от проблематичных правил вывода. Проблема нахождения полного набора аксиом, позволяющего выводить все уравнения между регулярными выражениями, интенсивно изучалась Джоном Хортоном Конвеем под названием "регулярные алгебры", однако большая часть его работы была бесконечной. В 1981 году Козен представил полную бесконечную систему уравнительной дедукции для алгебры регулярных языков. В 1994 году он предложил вышеуказанную конечную систему аксиом, использующую безусловные и условные равенства (при этом a ≤ b рассматривается как сокращение для a + b = b), которая является эквивалентно полной для алгебры регулярных языков, то есть два регулярных выражения a и b обозначают один и тот же язык только тогда, когда a = b выводится из вышеуказанных аксиом.

Обобщение (или отношение к другим структурам)

Алгебры Клини являются частным случаем замкнутых полуколец, также называемых квазирегулярными полукольцами или полукольцами Лемана, которые представляют собой полукольца, в которых для каждого элемента существует хотя бы одна квазиобратная, удовлетворяющая уравнению: a* = aa* + 1 = a*a + 1. Эта квазиобратная не обязательно единственна.