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

• Определение и свойства алгебры Клини

  • Алгебра Клини — это алгебра с операциями сложения, умножения и операции «звезда Клини». 
  • Операция «звезда Клини» является идемпотентной и монотонной, а также удовлетворяет определенным аксиомам. 
  • Алгебра Клини обладает свойствами, такими как нуль является наименьшим элементом и сумма является наименьшей верхней границей. 

• Примеры алгебр Клини

  • Примеры включают алгебры над конечными множествами, моноидами и линейными пространствами. 
  • Алгебры Клини могут быть использованы для описания регулярных выражений, обычных языков и детерминированных конечных автоматов. 

• История и развитие

  • Клини ввел понятие регулярных выражений и сформулировал некоторые их алгебраические законы. 
  • Редько и Саломаа внесли значительный вклад в аксиоматизацию алгебры обычных языков. 
  • Козен предложил полную систему аксиом для алгебры обычных языков, которая является уравнительно полной. 

• Обобщение и связь с другими структурами

  • Алгебры Клини являются частным случаем замкнутых полуколец, которые имеют квазиобратные элементы. 
  • Замкнутые полукольца и алгебры Клини связаны с задачами о путях, включая задачу о кратчайшем пути. 

• Рекомендации

  • Для дальнейшего чтения предлагается книга, в которой обсуждаются достижения в области алгебры Клини за последние 20 лет.