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

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

Определение

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

Алгебра Клини — это множество 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 : a 1 = 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 ^*) ≤ х ^[3]

Интуитивно можно думать о 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 \cdot W = интервал {v \cdot w | v \in V, w \in 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 . Это алгебра Клини с нулевым элементом +∞ и одним элементом — действительным числом ноль. Тогда взвешенный ориентированный граф можно рассматривать как детерминированный конечный автомат, в котором каждый переход помечен его весом. Для любых двух узлов графа (состояний автомата) регулярные выражения, вычисленные с помощью алгоритма Клини, в этой конкретной алгебре Клини оцениваются как кратчайшая длина пути между узлами. ^[4]

Характеристики

наименьший элемент: 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 ^*) п = ( кепка ) ^*. ^[5]

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

История

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

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

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

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

См. также

Ссылки

^ Марк Пули; Юрг Колас (2011). Общий вывод: объединяющая теория автоматического рассуждения . Джон Уайли и сыновья. п. 246. ИСБН 978-1-118-01086-0 .
^ Обзор см.: Козен, Декстер (1990). «Об алгебрах Клини и замкнутых полукольцах» (PDF) . В Роване, Бранислав (ред.). Математические основы информатики, Учеб. 15-й симпозиум, MFCS '90, Банска-Бистрица/Чехия. 1990 . Конспект лекций Информатика. Том. 452. Шпрингер-Верлаг . стр. 26–47. Збл 0732.03047 .
^ Козен (1990), разд.2.1, стр.3
^ Гросс, Джонатан Л.; Йеллен, Джей (2003), Справочник по теории графов , дискретной математике и ее приложениям, CRC Press, стр. 65, ISBN 9780203490204 .
^ Козен (1990), разд.2.1.2, стр.5
^ СК Клини (декабрь 1951 г.). Представление событий в нервных сетях и конечных автоматах (PDF) (Технический отчет). ВВС США/Корпорация РЭНД. п. 98. РМ-704. Здесь: разд.7.2, стр.52
^ Клини, Стивен К. (1956). «Представление событий в нервных сетях и конечных автоматах» (PDF) . Исследования автоматов, Анналы математических исследований . 34 . Принстонский университет. Нажимать. Здесь: разд.7.2, стр.26-27
^ Клини (1956), стр.35
^ В. Н. Редько (1964). «Об определяющих соотношениях для алгебры регулярных событий» (PDF) . Украинский математический журнал [ uk ] . 16 (1): 120–126. (на русском языке)
^ Арто Саломаа (январь 1966 г.). «Две полные системы аксиом алгебры регулярных событий» (PDF) . Журнал АКМ . 13 (1): 158–169. дои : 10.1145/321312.321326 . S2CID 8445404 .
^ Конвей, Дж. Х. (1971). Регулярная алгебра и конечные машины . Лондон: Чепмен и Холл. ISBN 0-412-10620-5 . Збл 0231.94041 . Глава IV.
^ Декстер Козен (1981). «На индукции против. ^*-непрерывность» (PDF) . В Декстере Козене (ред.). Proc. Workshop Logics of Programs . Lect. Notes in Comput. Sci. Vol. 131. Springer. стр. 167–176.
^ Декстер Козен (май 1994 г.). «Теорема полноты алгебр Клини и алгебры регулярных событий» (PDF) . Информация и вычисления . 110 (2): 366–390. дои : 10.1006/inco.1994.1037 . — Более ранняя версия выглядела как: Декстер Козен (май 1990 г.). Теорема полноты алгебр Клини и алгебры регулярных событий (Технический отчет). Корнелл. п. 27. ТР90-1123.
^ Джонатан С. Голан (30 июня 2003 г.). Полукольца и аффинные уравнения над ними . Springer Science & Business Media. стр. 157–159. ISBN 978-1-4020-1358-4 .
^ Перейти обратно: ^а ^б ^с Марк Пули; Юрг Колас (2011). Общий вывод: объединяющая теория автоматического рассуждения . Джон Уайли и сыновья. стр. 232 и 248. ISBN. 978-1-118-01086-0 .

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

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

[PoulyKohlas2012-1] Марк Пули; Юрг Колас (2011). Общий вывод: объединяющая теория автоматического рассуждения . Джон Уайли и сыновья. п. 246. ИСБН 978-1-118-01086-0 .

[2] Обзор см.: Козен, Декстер (1990). «Об алгебрах Клини и замкнутых полукольцах» (PDF) . В Роване, Бранислав (ред.). Математические основы информатики, Учеб. 15-й симпозиум, MFCS '90, Банска-Бистрица/Чехия. 1990 . Конспект лекций Информатика. Том. 452. Шпрингер-Верлаг . стр. 26–47. Збл 0732.03047 .

[3] Козен (1990), разд.2.1, стр.3

[4] Гросс, Джонатан Л.; Йеллен, Джей (2003), Справочник по теории графов , дискретной математике и ее приложениям, CRC Press, стр. 65, ISBN 9780203490204 .

[5] Козен (1990), разд.2.1.2, стр.5

[6] СК Клини (декабрь 1951 г.). Представление событий в нервных сетях и конечных автоматах (PDF) (Технический отчет). ВВС США/Корпорация РЭНД. п. 98. РМ-704. Здесь: разд.7.2, стр.52

[7] Клини, Стивен К. (1956). «Представление событий в нервных сетях и конечных автоматах» (PDF) . Исследования автоматов, Анналы математических исследований . 34 . Принстонский университет. Нажимать. Здесь: разд.7.2, стр.26-27

[8] Клини (1956), стр.35

[9] В. Н. Редько (1964). «Об определяющих соотношениях для алгебры регулярных событий» (PDF) . Украинский математический журнал [ uk ] . 16 (1): 120–126. (на русском языке)

[10] Арто Саломаа (январь 1966 г.). «Две полные системы аксиом алгебры регулярных событий» (PDF) . Журнал АКМ . 13 (1): 158–169. дои : 10.1145/321312.321326 . S2CID 8445404 .

[11] Конвей, Дж. Х. (1971). Регулярная алгебра и конечные машины . Лондон: Чепмен и Холл. ISBN 0-412-10620-5 . Збл 0231.94041 . Глава IV.

[12] Декстер Козен (1981). «На индукции против. ^*-непрерывность» (PDF) . В Декстере Козене (ред.). Proc. Workshop Logics of Programs . Lect. Notes in Comput. Sci. Vol. 131. Springer. стр. 167–176.

[13] Декстер Козен (май 1994 г.). «Теорема полноты алгебр Клини и алгебры регулярных событий» (PDF) . Информация и вычисления . 110 (2): 366–390. дои : 10.1006/inco.1994.1037 . — Более ранняя версия выглядела как: Декстер Козен (май 1990 г.). Теорема полноты алгебр Клини и алгебры регулярных событий (Технический отчет). Корнелл. п. 27. ТР90-1123.

[Golan2003-14] Джонатан С. Голан (30 июня 2003 г.). Полукольца и аффинные уравнения над ними . Springer Science & Business Media. стр. 157–159. ISBN 978-1-4020-1358-4 .

[PoulyKohlas2012b-15] Перейти обратно: ^а ^б ^с Марк Пули; Юрг Колас (2011). Общий вывод: объединяющая теория автоматического рассуждения . Джон Уайли и сыновья. стр. 232 и 248. ISBN. 978-1-118-01086-0 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]