Navigation
  • Home
  • Recent
  • Most Active
  • Popular
  • Blog
  • Credits
  • RSS
    		•
      Interaction
  • Register
  • Statistics
    		•
      Help
  • Suggestions
  • Contact Us
  • How to Edit
  • Help
    		•



    [Edit]


    In mathematics, a Kleene algebra (named after Stephen Cole Kleene, pronounced "clay-knee") is either of two different things:
      A bounded distributive lattice with an involution satisfying De Morgan's laws, and the inequality x∧−x ≤ y∨−y. Thus every Boolean algebra is a Kleene algebra, but most Kleene algebras are not Boolean algebras. Just as Boolean algebras are related to the classical propositional logic, Kleene algebras relate to Kleene's three-valued logic.

        Kleene algebra
            Definition
            Examples
            Properties
            History
            See also

    top

    Definition

    Various inequivalent definitions of Kleene algebras and related structures have been given in the literature. See 1 for a survey. Here we will give the definition that seems to be the most common nowadays.

    A Kleene algebra is a set A together with two binary operations +
    A × A → A and ·
    A × A → A and one function
      A → A, written as a + b, ab and a
        respectively, so that the following axioms are satisfied.
      Associativity of + and ·: a + (b + c) = (a + b) + c and a(bc) = (ab)c for all a, b, c in A.
      Distributivity: a(b + c) = (ab) + (ac) and (b + c)a = (ba) + (ca) for all a, b, c in A
      Identity elements for + and ·: There exists an element 0 in A such that for all a in A: a + 0 = 0 + a = a. There exists an element 1 in A such that for all a in A: a1 = 1a = a.
      a0 = 0a = 0 for all a in A.
    The above axioms define a semiring. We further require:
    It is now possible to define a partial order ≤ on A by setting a ≤ b iff a + b = b (or equivalently: a ≤ b iff there exists an x in A such that a + x = b). With this order we can formulate the last two axioms about the operation
      :
      1 + a(a
        ) ≤ a
          for all a in A.
      1 + (a
        )a ≤ a
          for all a in A.
      if a and x are in A such that ax ≤ x, then a
        x ≤ x
      if a and x are in A such that xa ≤ x, then x(a
        ) ≤ x

    Intuitively, one should think of a + b as the "union" or the "least upper bound" of a and b and of ab as some multiplication which is monotonic, in the sense that a ≤ b implies ax ≤ bx. The idea behind the star operator is a
      = 1 + a + aa + aaa + ... From the standpoint of programming theory, one may also interpret + as "choice", · as "sequencing" and
        as "iteration".

    top

    Examples

    Let Σ be a finite set (an "alphabet") and let A be the set of all regular expressions over Σ. We consider two such regular expressions equal if they describe the same language. Then A forms a Kleene algebra. In fact, this is a free Kleene algebra in the sense that any equation among regular expressions follows from the Kleene algebra axioms and is therefore valid in every Kleene algebra.

    Again let Σ be an alphabet. Let A be the set of all regular languages over Σ (or the set of all context-free languages over Σ; or the set of all recursive languages over Σ; or the set of all languages over Σ). Then the union (written as +) and the concatenation (written as ·) of two elements of A again belong to A, and so does the Kleene star operation applied to any element of A. We obtain a Kleene algebra A with 0 being the empty set and 1 being the set that only contains the empty string.

    Let M be a monoid with identity element e and let A be the set of all subsets of M. For two such subsets S and T, let S + T be the union of S and T and set ST = . S
      is defined as the submonoid of M generated by S, which can be described as ∪ S ∪ SS ∪ SSS ∪ ... Then A forms a Kleene algebra with 0 being the empty set and 1 being . An analogous construction can be performed for any small category.

    Suppose M is a set and A is the set of all binary relations on M. Taking + to be the union, · to be the composition and
      to be the reflexive transitive hull, we obtain a Kleene algebra.

    Every boolean algebra with operations v and ^ turns into a Kleene algebra if we use v for +, ^ for · and set a
      = 1 for all a.

    A quite different Kleene algebra is useful when computing shortest paths in weighted directed graphs: let A be the extended real number line, take a + b to be the minimum of a and b and ab to be the ordinary sum of a and b (with the sum of +∞ and -∞ being defined as +∞). a
      is defined to be the real number zero for nonnegative a and -∞ for negative a. This is a Kleene algebra with zero element +∞ and one element the real number zero.

    top

    Properties

    Zero is the smallest element: 0 ≤ a for all a in A.

    The sum a + b is the least upper bound of a and b: we have a ≤ a + b and b ≤ a + b and if x is an element of A with a ≤ x and b ≤ x, then a + b ≤ x. Similarly, a1 + ... + an is the least upper bound of the elements a1, ..., an.

    Multiplication and addition are monotonic: if a ≤ b, then a + x ≤ b + x, ax ≤ bx and xa ≤ xb for all x in A.

    Regarding the
      operation, we have 0
        = 1 and 1
          = 1, that
            is monotonic (a ≤ b implies a
              ≤ b
                ), and that an ≤ a
                  for every natural number n. Furthermore, (a
                    )(a
                      ) = a
                        , (a
                          )
                            = a
                              , and a ≤ b
                                if and only if a
                                  ≤ b
                                    .

    If A is a Kleene algebra and n is a natural number, then one can consider the set Mn(A) consisting of all n-by-n matrices with entries in A.
    Using the ordinary notions of matrix addition and multiplication, one can define a unique
      -operation so that Mn(A) becomes a Kleene algebra.

    top

    History

    Kleene algebras were not defined by Kleene; he introduced regular expressions and asked for a set of axioms which would allow to derive all equations among regular expressions. The axioms of Kleene algebras solve this problem, as was first shown by Dexter Kozen.

    top

    See also


     
    Search more:
     

       
    Source Privacy License Download Contact Us Atlas
    Scientus.org Dictionary (Yet Another Wiki) RC : 1.39
    MIT OpenCourseWare
    This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Kleene algebra". link