Thursday, 08 March 2012
In mathematics, a Kleene algebra ( ; named after Stephen Cole Kleene) is either of two different things:

A bounded distributive lattice with an involution satisfying De Morgan's laws (i.e. a De Morgan algebra), additionally satisfying the inequality ''x''∧−''x'' ≤ ''y''∨−''y''. Kleene (and De Morgan) algebras are subclasses of Ockham algebras. The simplest Kleene algebra of this kind is Kleene's three-valued logic K3. (This is analogous to Boolean logic being the simplest Boolean algebra.)

  • An algebraic structure that generalizes the operations known from regular expressions. The remainder of this article deals with this notion of Kleene algebra.

    • 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''.
  • Commutativity of +: ''a'' + ''b'' = ''b'' + ''a'' for all ''a'', ''b'' 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'': ''a''1 = 1''a'' = ''a''.
  • ''a''0 = 0''a'' = 0 for all ''a'' in ''A''.
    • The above axioms define a semiring. We further require:
  • + is idempotent: ''a'' + ''a'' = ''a'' for all ''a'' in ''A''.
    • It is now possible to define a partial order ≤ on ''A'' by setting ''a'' ≤ ''b'' if and only if ''a'' + ''b'' = ''b'' (or equivalently: ''a'' ≤ ''b'' if and only if 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 language theory, one may also interpret + as "choice", · as "sequencing" and * as "iteration".

    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'' = {''st'' : ''s'' in ''S'' and ''t'' in ''T''}. ''S''* is defined as the submonoid of ''M'' generated by ''S'', which can be described as {''e''} ∪ ''S'' ∪ ''SS'' ∪ ''SSS'' ∪ ... Then ''A'' forms a Kleene algebra with 0 being the empty set and 1 being {''e''}. 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 \lor and \land turns into a Kleene algebra if we use \lor for +, \land 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.

    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, ''a''1 + ... + ''a''''n'' is the least upper bound of the elements ''a''1, ..., ''a''''n''.

    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 ''a''''n'' ≤ ''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 M''n''(''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 M''n''(''A'') becomes a Kleene algebra.

    History

    Kleene algebras were not defined by Kleene; he introduced regular expressions and asked for a complete set of axioms which would allow derivation of all equations among regular expressions. The problem was first studied by John Horton Conway under the name of ''regular algebras''. The axioms of Kleene algebras solve this problem, as was first shown by Dexter Kozen.

    References

    # Dexter Kozen: ''On Kleene algebras and closed semirings.'' In Rovan, editor, Proc. Math. Found. Comput. Sci., volume 452 of Lecture Notes in Computer Science, pages 26–47. Springer, 1990. Online at http://www.cs.cornell.edu/~kozen/papers/kacs.ps # Dexter Kozen: CS786 Spring 04, Introduction to Kleene Algebra. http://www.cs.cornell.edu/Courses/cs786/2004sp/ # J.H. Conway, ''Regular algebra and finite machines'', Chapman and Hall, 1971, ISBN 0-412-10620-5. Chap.IV.

    See also

  • Action algebra
  • Algebraic structure
  • Kleene star
  • Regular expression

    • Category:Algebraic structures Category:Algebraic logic Category:Formal languages Category:Many-valued logic

    fr:Algèbre de Kleene pt:Álgebra de Kleene ru:Алгебра Клини sr:Klinijeva algebra zh:克莱尼代数

    This text is licensed under the Creative Commons CC-BY-SA License. This text was originally published on Wikipedia and was developed by the Wikipedia community.



    show more
    add to playlist
    clear
    Video Suggestions







    The World News (WN) Network, has created this privacy statement in order to demonstrate our firm commitment to user privacy. The following discloses our information gathering and dissemination practices for wn.com, as well as e-mail newsletters.

    1. Personal Information Collection and Use

    We do not collect personally identifiable information about you, except when you provide it to us. For example, if you submit an inquiry to us or sign up for our newsletter, you may be asked to provide certain information such as your contact details (name, e-mail address, mailing address, etc.).

    When you submit your personally identifiable information through wn.com, you are giving your consent to the collection, use and disclosure of your personal information as set forth in this Privacy Policy. If you would prefer that we not collect any personally identifiable information from you, please do not provide us with any such information. We will not sell or rent your personally identifiable information to third parties without your consent, except as otherwise disclosed in this Privacy Policy.

    Except as otherwise disclosed in this Privacy Policy, we will use the information you provide us only for the purpose of responding to your inquiry or in connection with the service for which you provided such information. We may forward your contact information and inquiry to our affiliates and other divisions of our company that we feel can best address your inquiry or provide you with the requested service. We may also use the information you provide in aggregate form for internal business purposes, such as generating statistics and developing marketing plans. We may share or transfer such non-personally identifiable information with or to our affiliates, licensees, agents and partners.

    We may retain other companies and individuals to perform functions on our behalf. Such third parties may be provided with access to personally identifiable information needed to perform their functions, but may not use such information for any other purpose.

    In addition, we may disclose any information, including personally identifiable information, we deem necessary, in our sole discretion, to comply with any applicable law, regulation, legal proceeding or governmental request.

    2. E-mail addresses

    We do not want you to receive unwanted e-mail from us. We try to make it easy to opt-out of any service you have asked to receive. If you sign-up to our e-mail newsletters we do not sell, exchange or give your e-mail address to a third party.

    E-mail addresses are collected via the wn.com web site. Users have to physically opt-in to receive the wn.com newsletter and a verification e-mail is sent. wn.com is clearly and conspicuously named at the point of

    collection.

    If you no longer wish to receive our newsletter and promotional communications, you may opt-out of receiving them by following the instructions included in each newsletter or communication or by e-mailing us at michaelw(at)wn.com

    The security of your personal information is important to us. We follow generally accepted industry standards to protect the personal information submitted to us, both during registration and once we receive it. No method of transmission over the Internet, or method of electronic storage, is 100 percent secure, however. Therefore, though we strive to use commercially acceptable means to protect your personal information, we cannot guarantee its absolute security.

    If we decide to change our e-mail practices, we will post those changes to this privacy statement, the homepage, and other places we think appropriate so that you are aware of what information we collect, how we use it, and under what circumstances, if any, we disclose it.

    If we make material changes to our e-mail practices, we will notify you here, by e-mail, and by means of a notice on our home page.

    3. Third Party Advertisers

    The advertising banners and other forms of advertising appearing on this Web site are sometimes delivered to you, on our behalf, by a third party. In the course of serving advertisements to this site, the third party may place or recognize a unique cookie on your browser. For more information on cookies, you can visit www.cookiecentral.com.

    4. Business Transfers

    As we continue to develop our business, we might sell certain aspects of our entities or assets. In such transactions, user information, including personally identifiable information, generally is one of the transferred business assets, and by submitting your personal information on Wn.com you agree that your data may be transferred to such parties in these circumstances.