Оглавление
Алгебра Клини
-
Определение и свойства алгебры Клини
- Алгебра Клини – это алгебра с операциями сложения, умножения и операции “звезда Клини”.
- Операция “звезда Клини” является идемпотентной и монотонной, а также удовлетворяет определенным аксиомам.
- Алгебра Клини обладает свойствами, такими как нуль является наименьшим элементом и сумма является наименьшей верхней границей.
-
Примеры алгебр Клини
- Примеры включают алгебры над конечными множествами, моноидами и линейными пространствами.
- Алгебры Клини могут быть использованы для описания регулярных выражений, обычных языков и детерминированных конечных автоматов.
-
История и развитие
- Клини ввел понятие регулярных выражений и сформулировал некоторые их алгебраические законы.
- Редько и Саломаа внесли значительный вклад в аксиоматизацию алгебры обычных языков.
- Козен предложил полную систему аксиом для алгебры обычных языков, которая является уравнительно полной.
-
Обобщение и связь с другими структурами
- Алгебры Клини являются частным случаем замкнутых полуколец, которые имеют квазиобратные элементы.
- Замкнутые полукольца и алгебры Клини связаны с задачами о путях, включая задачу о кратчайшем пути.
-
Рекомендации
- Для дальнейшего чтения предлагается книга, в которой обсуждаются достижения в области алгебры Клини за последние 20 лет.
Полный текст статьи: