Interface KleeneAlgebra<E>

All Superinterfaces:
AbelianMonoid<E>, Magma<E>, Monoid<E>, Semiring<E>, Set<E>
public interface KleeneAlgebra<E> extends Semiring<E>
A Kleene Algebra is an idempotent semiring with a closure operator (Kleene star).

It is used in theoretical computer science to model regular expressions, finite automata, and program semantics.

Mathematical Definition

A Kleene algebra (K, +, ·, *, 0, 1) is an idempotent semiring (a + a = a) equipped with a unary operation * satisfying:

  • 1 + a · a* ≤ a*
  • 1 + a* · a ≤ a*
  • b + a · x ≤ x ⇒ a* · b ≤ x
  • b + x · a ≤ x ⇒ b · a* ≤ x
where a ≤ b is defined as a + b = b.

References

  • Stephen Cole Kleene, "Representation of Events in Nerve Nets and Finite Automata", in Automata Studies, Princeton University Press, 1956, pp. 3-41
  • Dexter Kozen, "A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events", Information and Computation, Vol. 110, No. 2, 1994, pp. 366-390
Since:
1.0
Author:
Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

  • Method Details

    • star

      E star(E a)
      The Kleene star operator (closure). Represents zero or more repetitions of the element.
      Parameters:
      a - the element
      Returns:
      a*

    • plus

      default E plus(E a)
      The plus operator (a+ = a · a*). Represents one or more repetitions.
      Parameters:
      a - the element
      Returns:
      a+