Алгебра Клини

Эта статья об алгебре Клини с операцией замыкания — обобщении регулярных выражений. Об алгебре Клини с инволюцией — обобщении тернарной логики Клини — см. «Алгебра Клини (с инволюцией)» .

В математике алгебра Клини ( / ˈk l eɪ n , i / KLAY -nee ; названа в честь Стивена Коула Клини ) — это идемпотентное (и, следовательно, частично упорядоченное) полукольцо наделенное оператором замыкания . Он обобщает операции, известные из регулярных выражений .

Определение

В литературе даны различные неэквивалентные определения алгебр Клини и родственных им структур. Здесь мы дадим определение, которое, по-видимому, является наиболее распространенным в настоящее время.

Алгебра Клини — это множество A вместе с двумя бинарными операциями + : A × A → A и · : A × A → A и одной функцией. ^* : A → A , записывается как a + b , ab и a ^* соответственно, так что выполняются следующие аксиомы.

• Ассоциативность + и ·: a + ( b + c ) = ( a + b + c и a ( bc ) = ( ab ) c для всех a , b , c в A. )
• Коммутативность +: a + b = b + a для всех a , b в A
• Дистрибутивность : a ( b + c ) = ( ab ) + ( ac ) и ( b + c ) a = ( ba ) + ( ca ) для всех a , b , c в A
• Тождественные элементы для + и ·: Существует элемент 0 в A такой, что для всех a в A : a + 0 = 0 + a = a . Существует элемент 1 в A такой, что для всех a в A : a1 = 1 a = a .
• Аннигиляция 0: a 0 = 0 a = 0 для всех a в A .

Приведенные выше аксиомы определяют полукольцо . Далее нам требуется:

• + идемпотентен : a + a = a всех a из A. для

Теперь можно определить частичный порядок ≤ на A , установив a ≤ b тогда и только тогда, когда a + b = b (или, что то же самое: a ≤ b тогда и только тогда, когда существует x в A такой, что a + x = b ; при любом определении a ⩽ b ⩽ a подразумевает a = b ); Используя этот порядок, мы можем сформулировать последние четыре аксиомы операции ^* :

• 1 + а ( а ^* ) ≤ а ^* для a в A. всех
• 1 + ( а ^* ) а ≤ а ^* для a в A. всех
• если a и x находятся в A такие, что ax ≤ x , то a ^* х ≤ х
• если a и x находятся в A такие, что xa ≤ x , то x ( a ^* ) ≤ х

Интуитивно можно представить a + b как «объединение» или «наименьшую верхнюю границу» a и b , а ab умножение — как некоторое монотонное в том смысле, что из a ≤ b следует ax ≤ bx . Идея звездного оператора заключается в ^* = 1 + a + aa + aaa + ... С точки зрения теории языков программирования + можно также интерпретировать как «выбор», · как «последовательность» и ^* как «итерация».

Примеры

Обозначительное соответствие между

Алгебры Клини и	+	·	*	0	1
Регулярные выражения	|	не написано	*	∅	е

Пусть Σ — конечное множество («алфавит») и пусть A — множество всех регулярных выражений над Σ. Мы считаем два таких регулярных выражения равными, если они описывают один и тот же язык . Тогда A образует алгебру Клини. Фактически, это свободная алгебра Клини в том смысле, что любое уравнение среди регулярных выражений следует из аксиом алгебры Клини и, следовательно, справедливо в любой алгебре Клини.

И снова пусть Σ — алфавит. Пусть A — множество всех регулярных языков над Σ (или множество всех контекстно-свободных языков над Σ; или множество всех рекурсивных языков над Σ; или множество всех языков над Σ). Тогда объединение (записанное как +) и конкатенация (записанное как ·) двух элементов A снова принадлежат A , как и операция звезды Клини , применяемая к любому элементу A . Мы получаем алгебру Клини A , где 0 — пустое множество , а 1 — множество, содержащее только пустую строку .

Пусть M — моноид с единичным элементом , и пусть A — множество всех подмножеств M e . Для двух таких подмножеств S и T пусть S + T будет объединением S и T и положим ST = { st : s в S и t в T }. С ^* определяется как субмоноид M, порожденный S , который можно описать как { e } ∪ S ∪ SS ∪ SSS ∪ ... Тогда A образует алгебру Клини, где 0 представляет собой пустое множество, а 1 представляет собой { e }. Аналогичную конструкцию можно провести для любой малой категории .

Линейные подпространства единичной алгебры над полем образуют алгебру Клини. Учитывая линейные подпространства V и W , определите V + W как сумму двух подпространств, а 0 как тривиальное подпространство {0}. Определим V · W = интервал {v · w | v ∈ V, w ∈ W} — линейная оболочка произведения векторов из V и W соответственно. Определите 1 = span {I} , размер единицы алгебры. Замыкание V является прямой суммой всех степеней V .

$$V^{*}=\bigoplus _{i=0}^{\infty }V^{i}$$

Предположим, что — множество, а A — множество всех бинарных отношений на M. M Приняв + за союз, · за композицию и ^* чтобы быть рефлексивным транзитивным замыканием , мы получаем алгебру Клини.

Любая булева алгебра с операциями $\lor$ и $\land$ превращается в алгебру Клини, если мы воспользуемся $\lor$ для +, $\land$ для · и установите ^* = 1 для всех a .

Совершенно другая алгебра Клини может быть использована для реализации алгоритма Флойда-Уоршалла , вычисляющего длину кратчайшего пути для каждых двух вершин взвешенного ориентированного графа , с помощью алгоритма Клини , вычисляющего регулярное выражение для каждых двух состояний детерминированного конечного автомата .Используя расширенную линию действительных чисел , возьмите a + b за минимум a и b , а ab за обычную сумму a и b (при этом сумма +∞ и −∞ определяется как +∞). а ^* определяется как действительное число ноль для неотрицательного a и −∞ для отрицательного a . Это алгебра Клини с нулевым элементом +∞ и одним элементом — действительным числом ноль. Тогда взвешенный ориентированный граф можно рассматривать как детерминированный конечный автомат, в котором каждый переход помечен его весом.Для любых двух узлов графа (состояний автомата) регулярные выражения, вычисленные с помощью алгоритма Клини, в этой конкретной алгебре Клини оцениваются как кратчайшая длина пути между узлами.

Свойства

наименьший элемент: 0 ≤ a для всех a в A. Ноль —

Сумма a + b — это наименьшая верхняя граница a и b : у нас есть a ≤ a + b и b ≤ a + b , и если x — элемент A с a ≤ x и b ≤ x , то a + b ≤ х . Аналогично, a ₁ + ... + является _an наименьшей верхней границей элементов a ₁ , ... an _, .

Умножение и сложение монотонны: если a ≤ b , то

• а + х ≤ б + х ,
• ax ≤ bx и
• ха ≤ xb

для x в A. всех

Что касается операции «звезда», у нас есть

• 0 ^* = 1 и 1 ^* = 1,
• a ≤ b подразумевает a ^* ≤ б ^* (монотонность),
• а ^н ≤ а ^* для каждого натурального числа n , где a ^н определяется как n -кратное умножение a ,
• ( а ^* )( а ^* ) = а ^* ,
• ( а ^* ) ^* = а ^* ,
• 1 + а ( а ^* ) = а ^* = 1 + ( а ^* ) а ,
• ax = xb подразумевает ( a ^* ) x = x ( б ^* ),
• (( аб ) ^* ) а = а (( не ) ^* ),
• ( а + б ) ^* = а ^* ( б ( а ^* )) ^* , и
• pq = 1 = qp влечет q ( a ^* ) п = ( кепка ) ^* .

Если A — алгебра Клини, а n — натуральное число, то можно рассматривать множество M _n ( A ), состоящее из всех размером n × n матриц с элементами A. из Используя обычные понятия сложения и умножения матриц, можно определить уникальную ^* -операция так, что M _n ( A ) становится алгеброй Клини.

История

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

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

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

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

См. также

• Алгебра действий
• Алгебраическая структура
• Клини звезда
• Регулярное выражение
• Звездное полукольцо
• Алгебра оценки

Примечания и ссылки

• Козен, Декстер . «CS786 Spring 04. Введение в алгебру Клини» .

Дальнейшее чтение

• Питер Хёфнер (2009). Алгебраические исчисления для гибридных систем . Совет директоров – Книги по запросу. стр. 10–13. ISBN  978-3-8391-2510-6 . Во введении к этой книге рассматриваются достижения в области алгебры Клини, достигнутые за последние 20 лет, которые не обсуждаются в статье выше.