Клини алгебра - Kleene algebra

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

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

Определение

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

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

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

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

  • 1 + а(а*) ≤ а* для всех а в А.
  • 1 + (а*)а ≤ а* для всех а в А.
  • если а и Икс находятся в А такой, что топор ≤ Икс, тогда а*Икс ≤ Икс
  • если а и Икс находятся в А такой, что ха ≤ Икс, тогда Икс(а*) ≤ Икс [3]

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

Примеры

Обозначение соответствия между
Клини алгебры и+·*01
Обычные выражения|не написано*∅ε

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

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

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

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

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

Каждые Булева алгебра с операциями и превращается в алгебру Клини, если мы используем для +, для · и установите а* = 1 для всех а.

Совершенно другая алгебра Клини может быть использована для реализации Алгоритм Флойда – Уоршолла, вычисляя длина кратчайшего пути для каждых двух вершин взвешенный ориентированный граф, от Алгоритм Клини, вычисляя регулярное выражение для каждых двух состояний детерминированный конечный автомат.С использованием расширенная строка действительных чисел возьми а + б быть минимумом а и б и ab быть обычной суммой а и б (сумма + ∞ и −∞ определяется как + ∞). а* определяется как действительное число ноль для неотрицательных а и −∞ для отрицательных а. Это алгебра Клини с нулевым элементом + ∞ и одним элементом - вещественным числом ноль. Взвешенный ориентированный граф затем можно рассматривать как детерминированный конечный автомат, где каждый переход помечен своим весом. Для любых двух узлов графа (состояний автомата) регулярные выражения, вычисленные с помощью алгоритма Клини, вычисляют, в этой конкретной алгебре Клини, до кратчайшего длина пути между узлами.[4]

Свойства

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

Сумма а + б это наименьшая верхняя граница из а и б: у нас есть а ≤ а + б и б ≤ а + б и если Икс является элементом А с участием а ≤ Икс и б ≤ Икс, тогда а + б ≤ Икс. Так же, а1 + ... + ап - точная верхняя граница элементов а1, ..., ап.

Умножение и сложение монотонны: если а ≤ б, тогда

  • а + Икс ≤ б + Икс,
  • топор ≤ bx, и
  • ха ≤ xb

для всех Икс в А.

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

  • 0* = 1 и 1* = 1,
  • а ≤ б подразумевает а* ≤ б* (монотонность),
  • ап ≤ а* для каждого натурального числа п, где ап определяется как п-кратное умножение а,
  • (а*)(а*) = а*,
  • (а*)* = а*,
  • 1 + а(а*) = а* = 1 + (а*)а,
  • топор = xb подразумевает (а*)Икс = Икс(б*),
  • ((ab)*)а = а((ба)*),
  • (а+б)* = а*(б(а*))*, и
  • pq = 1 = qp подразумевает q(а*)п = (qap)*.[5]

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

История

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

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

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

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

Смотрите также

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

  1. ^ Марк Пули; Юрг Колас (2011). Общий вывод: объединяющая теория автоматизированных рассуждений. Джон Вили и сыновья. п. 246. ISBN  978-1-118-01086-0.
  2. ^ Для обзора см: Козен, Декстер (1990). «Об алгебрах Клини и замкнутых полукольцах» (PDF). В Роване, Бранислав (ред.). Математические основы информатики, Учеб. 15-й симпозиум, MFCS '90, Банска-Бистрица / Чехия. 1990 г.. Конспект лекций Информатика. 452. Springer-Verlag. С. 26–47. Zbl  0732.03047.
  3. ^ Козен (1990), раздел 2.1, стр.3
  4. ^ Гросс, Джонатан Л .; Йеллен, Джей (2003), Справочник по теории графов, Дискретная математика и ее приложения, CRC Press, стр. 65, ISBN  9780203490204.
  5. ^ Козен (1990), раздел 2.1.2, стр.5
  6. ^ S.C. Kleene (декабрь 1951 г.). Представление событий в нервных сетях и конечных автоматах (PDF) (Технический отчет). ВВС США / RAND Corporation. п. 98. RM-704. Здесь: раздел 7.2, стр.52
  7. ^ Клини, Стивен С. (1956). «Представление событий в нервных сетях и конечных автоматах» (PDF). Исследования автоматов, Анналы математических исследований. Princeton Univ. Нажмите. 34. Здесь: раздел 7.2, с.26-27
  8. ^ Клини (1956), стр.35
  9. ^ В.Н. Редько (1964). «Об определении соотношений для алгебры регулярных событий» (PDF). Украинский математический журнал [Великобритания ]. 16 (1): 120–126. (По-русски)
  10. ^ Арто Саломаа (Январь 1966 г.). «Две полные системы аксиом алгебры регулярных событий» (PDF). Журнал ACM. 13 (1): 158–169. Дои:10.1145/321312.321326.
  11. ^ Конвей, Дж. (1971). Регулярная алгебра и конечные машины. Лондон: Чепмен и Холл. ISBN  0-412-10620-5. Zbl  0231.94041. Глава IV.
  12. ^ Декстер Козен (1981). "Индукция vs. *-прерывность " (PDF). В Декстер Козен (ред.). Proc. Практическая логика программ. Лект. Примечания в Comput. Sci. 131. Springer. С. 167–176.
  13. ^ учитывая а≤б как сокращение для а+б=б
  14. ^ Декстер Козен (май 1994). "Теорема полноты для алгебр Клини и алгебры регулярных событий" (PDF). Информация и вычисления. 110 (2): 366–390. Дои:10.1006 / inco.1994.1037. - Более ранняя версия выглядела как: Декстер Козен (май 1990 г.). Теорема полноты для алгебр Клини и алгебры регулярных событий (Технический отчет). Корнелл. п. 27. TR90-1123.
  15. ^ Джонатан С. Голан (30 июня 2003 г.). Полукольца и аффинные уравнения над ними. Springer Science & Business Media. С. 157–159. ISBN  978-1-4020-1358-4.
  16. ^ а б c Марк Пули; Юрг Колас (2011). Общий вывод: объединяющая теория для автоматизированных рассуждений. Джон Вили и сыновья. С. 232 и 248. ISBN  978-1-118-01086-0.

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