Алгебра Клини - Kleene algebra
В математике , А клиниевская алгебра ( / к л eɪ н я / Klay -nee , названный в честь Клини ) является идемпотентным (и , таким образом , частично упорядоченным) полукольцами , снабженным оператором замыкания . Он обобщает операции, известные из регулярных выражений .
Определение
В литературе были даны различные неэквивалентные определения алгебр Клини и родственных структур. Здесь мы дадим определение, которое кажется наиболее распространенным в настоящее время.
Алгебра Клини - это множество 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
Интуитивно следует думать о 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 представляет собой набор и есть множество всех бинарных отношений на М . Принимая + за объединение, · за композицию и * за рефлексивное транзитивное замыкание , мы получаем алгебру Клини.
Каждая булева алгебра с операциями и превращается в алгебру Клини, если мы используем for +, for · и положим a * = 1 для всех a .
Совершенно другая алгебра Клини может быть использована для реализации алгоритма Флойда – Уоршалла , вычисляющего длину кратчайшего пути для каждых двух вершин взвешенного ориентированного графа с помощью алгоритма Клини , вычисляющего регулярное выражение для каждых двух состояний детерминированного конечного автомата . Используя расширенную линию действительных чисел , возьмем a + b как минимум a и b, а ab как обычную сумму a и b (с суммой + ∞ и −∞, определяемой как + ∞). a * определяется как действительное число ноль для неотрицательного a и −∞ для отрицательного a . Это алгебра Клини с нулевым элементом + ∞ и одним элементом - вещественным числом ноль. Тогда взвешенный ориентированный граф можно рассматривать как детерминированный конечный автомат, в котором каждый переход помечен своим весом. Для любых двух узлов графа (состояний автомата) регулярные выражения, вычисленные на основе алгоритма Клини, оценивают, в этой конкретной алгебре Клини, длину кратчайшего пути между узлами.
Свойства
Ноль является наименьшим элементом: 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 ) * .
Если алгебра Клини и п представляет собой натуральное число, то можно рассматривать множество М п ( А ) , состоящие из всех 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.
Замкнутые полукольца и алгебры Клини появляются в задачах алгебраических путей , являющихся обобщением проблемы кратчайшего пути .
Смотрите также
- Алгебра действий
- Алгебраическая структура
- Клини звезда
- Регулярное выражение
- Звездное полукольцо
- Алгебра оценки
Примечания и ссылки
дальнейшее чтение
- Петер Хёфнер (2009). Алгебраические исчисления для гибридных систем . Совет директоров - Книги по запросу. С. 10–13. ISBN 978-3-8391-2510-6 . Во введении к этой книге рассматриваются достижения в области алгебры Клини за последние 20 лет, которые не обсуждаются в статье выше.