В математике , А клиниевская алгебра ( / к л eɪ н я / Klay -nee , названный в честь Клини ) является идемпотентным (и , таким образом , частично упорядоченным) полукольцами , снабженным оператором замыкания . [1] Он обобщает операции, известные из регулярных выражений .
Определение
В литературе были даны различные неэквивалентные определения алгебр Клини и родственных структур. [2] Здесь мы дадим определение, которое кажется наиболее распространенным в настоящее время.
Алгебра Клини - это множество A вместе с двумя бинарными операциями +: A × A → A и ·: A × A → A и одной функцией * : A → A , записанной как a + b , ab и a * соответственно, так что выполняются следующие аксиомы.
- Ассоциативность + и ·: + ( Ь + с ) = ( + б ) + с и ( BC ) = ( AB ) с для всех с , Ь , с в 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 . В A существует элемент 1 такой, что для всех a в A : a 1 = 1 a = a .
- Аннигиляционное от 0: 0 = 0 = 0 для всех а в А .
Приведенные выше аксиомы определяют полукольцо . Мы также требуем:
- + Является идемпотентным : + = для всех а в А .
Теперь можно определить частичный порядок ≤ на A , установив a ≤ b тогда и только тогда, когда a + b = b (или эквивалентно: a ≤ b тогда и только тогда, когда существует x в A такой, что a + x = b ; при любом определении из a ≤ b ≤ a следует a = b ). В этом порядке мы можем сформулировать последние четыре аксиомы об операции * :
- 1 + ( * ) ≤ * для всех а в А .
- 1 + ( * ) ≤ * для всех а в А .
- если a и x находятся в A такие, что ax ≤ x , то a * x ≤ x
- если a и x находятся в A такие, что xa ≤ x , то x ( a * ) ≤ x [3]
Интуитивно следует думать о a + b как о «объединении» или «наименьшей верхней границе» a и b, а ab как о некотором монотонном умножении в том смысле, что a ≤ b влечет ax ≤ bx . Идея, лежащая в основе оператора звезды, такова: a * = 1 + a + aa + aaa + ... С точки зрения теории языков программирования , можно также интерпретировать + как «выбор», · как «последовательность» и * как «итерацию». .
Примеры
Клини алгебры и | + | · | * | 0 | 1 |
---|---|---|---|---|---|
Регулярные выражения | | | не написано | * | ∅ | ε |
Пусть Σ - конечное множество («алфавит») и пусть A - множество всех регулярных выражений над Σ. Мы считаем два таких регулярных выражения равными, если они описывают один и тот же язык . Тогда A образует алгебру Клини. Фактически, это свободная алгебра Клини в том смысле, что любое уравнение среди регулярных выражений следует из аксиом алгебры Клини и, следовательно, справедливо в любой алгебре Клини.
Снова пусть Σ - алфавит. Пусть A - множество всех регулярных языков над Σ (или множество всех контекстно-свободных языков над Σ; или множество всех рекурсивных языков над Σ; или множество всех языков над Σ). Тогда объединение (записывается как +) и конкатенации (записывается в виде ·) из двух элементов A снова принадлежат к А , и так же звезда Клини операция применяется к любому элементу A . Мы получаем алгебру Клини A, где 0 - это пустое множество, а 1 - это набор, который содержит только пустую строку .
Пусть М будет Моноидом с единицей е и пусть множество всех подмножеств из М . Для двух таких подмножеств S и T пусть S + T будет объединением S и T, и положим ST = { st : s в S и t в T }. S * определяется как подмоноид M, порожденный S , который можно описать как { e } ∪ S ∪ SS ∪ SSS ∪ ... Тогда A образует алгебру Клини, где 0 является пустым множеством, а 1 - { e }. Аналогичное построение можно выполнить для любой малой категории .
В линейные подпространства из унитальной алгебры над полем образуют алгебру Клини. Для линейных подпространств V и W определим V + W как сумму двух подпространств, а 0 как тривиальное подпространство {0}. Определим V · W = span {v · w | v ∈ V, w ∈ W}, линейная оболочка произведения векторов из V и W соответственно. Определите 1 = span {I}, промежуток единицы алгебры. Замыкание V является прямой суммой всех степеней V .
Пусть M представляет собой набор и есть множество всех бинарных отношений на М . Принимая + за объединение, · за композицию и * за рефлексивное транзитивное замыкание , мы получаем алгебру Клини.
Каждая булева алгебра с операциями а также превращается в алгебру Клини, если мы используем для +, для · и установить a * = 1 для всех a .
Совершенно другая алгебра Клини может быть использована для реализации алгоритма Флойда – Уоршалла , вычисляющего длину кратчайшего пути для каждых двух вершин взвешенного ориентированного графа с помощью алгоритма Клини , вычисляющего регулярное выражение для каждых двух состояний детерминированного конечного автомата . Используя расширенную строку действительных чисел , возьмем a + b как минимум a и b, а ab как обычную сумму a и b (с суммой + ∞ и −∞, определяемой как + ∞). a * определяется как действительное число ноль для неотрицательного a и −∞ для отрицательного a . Это алгебра Клини с нулевым элементом + ∞ и одним элементом - вещественным числом ноль. Взвешенный ориентированный граф можно рассматривать как детерминированный конечный автомат, в котором каждый переход помечен своим весом. Для любых двух узлов графа (состояний автомата) регулярные выражения, вычисленные на основе алгоритма Клини, вычисляют, в этой конкретной алгебре Клини, длину кратчайшего пути между узлами. [4]
Характеристики
Ноль является наименьшим элементом: 0 ≤ для всех а в А .
Сумма + Ь является не менее верхняя граница из с и Ь : мы имеем в ≤ а + б , а б ≤ + б , а если х является элементом А с более ≤ х и б ≤ х , то в + б ≤ х . Аналогично, a 1 + ... + a n - наименьшая верхняя граница элементов a 1 , ..., a n .
Умножение и сложение монотонны: если a ≤ b , то
- а + х ≤ б + х ,
- ax ≤ bx и
- xa ≤ xb
для всех х в А .
Что касается звездной операции, у нас есть
- 0 * = 1 и 1 * = 1,
- a ≤ b влечет a * ≤ b * (монотонность),
- п ≤ * для любого натурального числа п , где п определяются как п - кратное умножения ,
- ( а * ) ( а * ) = а * ,
- ( а * ) * = а * ,
- 1 + а ( а * ) = а * = 1 + ( а * ) а ,
- ax = xb влечет ( a * ) x = x ( b * ),
- (( ab ) * ) a = a (( ba ) * ),
- ( a + b ) * = a * ( b ( a * )) * , и
- pq = 1 = qp влечет q ( a * ) p = ( qap ) * . [5]
Если алгебра Клини и п представляет собой натуральное число, то можно рассматривать множество М п ( А ) , состоящие из всех 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. ISBN. 978-1-118-01086-0.
- ^ Для обзора см: Козен, Декстер (1990). «Об алгебрах Клини и замкнутых полукольцах» (PDF) . В Роване, Бранислав (ред.). Математические основы информатики, Учеб. 15-й симпозиум, MFCS '90, Банска-Бистрица / Чехия. 1990 . Конспект лекций Информатика. 452 . Springer-Verlag . С. 26–47. Zbl 0732.03047 .
- ^ Кодзэн (1990), sect.2.1, стр.3
- ^ Гросс, Джонатан Л .; Йеллен, Джей (2003), Справочник по теории графов , дискретной математике и ее приложениям, CRC Press, стр. 65, ISBN 9780203490204.
- ^ Кодзэн (1990), sect.2.1.2, стр.5
- ^ SC Kleene (декабрь 1951 г.). Представление событий в нервных сетях и конечных автоматах (PDF) (Технический отчет). ВВС США / RAND Corporation. п. 98. РМ-704. Здесь: раздел 7.2, стр.52
- ^ Клини, Стивен С. (1956). «Представление событий в нервных сетях и конечных автоматах» (PDF) . Автоматы, Анналы математических исследований . Princeton Univ. Нажмите. 34 . Здесь: раздел 7.2, с.26-27
- Перейти ↑ Kleene (1956), p.35
- ^ В. Н. Редько (1964). «Об определении соотношений для алгебры регулярных событий» (PDF) . Украинский математический журнал . 16 (1): 120–126. (На русском)
- ^ Арто Саломаа (январь 1966 г.). «Две полные системы аксиом для алгебры регулярных событий» (PDF) . Журнал ACM . 13 (1): 158–169. DOI : 10.1145 / 321312.321326 .
- ^ Конвей, Дж. Х (1971). Регулярная алгебра и конечные машины . Лондон: Чепмен и Холл. ISBN 0-412-10620-5. Zbl 0231.94041 . Глава IV.
- ^ Декстер Козен (1981). «Об индукции против * -прерывности» (PDF) . В Декстер Козен (ред.). Proc. Мастерская "Логика программ" . Лект. Заметки в Comput. Sci. 131 . Springer. С. 167–176.
- ^ Декстер Козен (май 1994). "Теорема полноты для алгебр Клини и алгебры регулярных событий" (PDF) . Информация и вычисления . 110 (2): 366–390. DOI : 10.1006 / inco.1994.1037 . - Более ранняя версия выглядела как: Декстер Козен (май 1990 г.). Теорема полноты для алгебр Клини и алгебры регулярных событий (Технический отчет). Корнелл. п. 27. TR90-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 Весна 04, Введение в алгебру Клини" .
дальнейшее чтение
- Петер Хёфнер (2009). Алгебраические исчисления для гибридных систем . Совет директоров - Книги по запросу. С. 10–13. ISBN 978-3-8391-2510-6. Во введении к этой книге рассматриваются достижения в области алгебры Клини за последние 20 лет, которые не обсуждаются в статье выше.