Kleene modules and linear languages

AbstractA 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 :