Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
432110 | The Journal of Logic and Algebraic Programming | 2006 | 10 Pages |
Abstract
A Kleene algebra (K, +, ·, *, 0, 1) is an idempotent semiring with an iteration * as axiomatised by Kozen. We consider left semiring modules (A, +, 0, :) over Kleene algebras. We call such a left semiring module a Kleene module if each linear equation x = a + r : x has a least solution, where : is the product from K × A to A. The linear context-free languages can be viewed as a Kleene module A over a Kleene algebra R of binary regular word relations. Thus, the simultaneous linear fixed-point operator μ on languages can be reduced to iteration * on R and the scalar product :.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics