![]() |
Kleene algebra
Kleene algebra (/ˈkleɪni/ KLAY-nee; named after Stephen Cole Kleene)
is an idempotent (and thus partially ordered) semiring endowed with a closure operator.[1] It generalizes the operations known from regular expressions. Various inequivalent definitions of Kleene algebras and related structures have been given in the literature.[2] 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. Wiki 1. Definition A Kleene algebra is a de Morgan algebra D satisfying x∧¬x≤y∨¬y for all x,y∈D. Since the order is definable in terms of the lattice operators, this can be stated as the equation x∧¬x∧(y∨¬y)=x∧¬x. 2. Examples Any Boolean algebra is a Kleene algebra, with ¬ the logical negation. The unit interval [0,1] is a Kleene algebra, with ¬x=(1−x). https://ncatlab.org/nlab/show/Kleene+algebra |
Kleene algebras are a particular case of closed semirings,
also called quasi-regular semirings or Lehmann semirings, which are semirings in which every element has at least one quasi-inverse satisfying the equation: a* = aa* + 1 = a*a + 1. This quasi-inverse is not necessarily unique.[14][15] In a Kleene algebra, a* is the least solution to the fixpoint equations: X = aX + 1 and X = Xa + 1.[15] Closed semirings and Kleene algebras appear in algebraic path problems, a generalization of the shortest path problem.[15] Wiki |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 08:33 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha