Kleene modules and linear languages |
| |
Authors: | Hans Leiß |
| |
Affiliation: | Centrum für Informations- und Sprachverarbeitung, Universität München, Oettingenstrasse 67, D-80538 München, Germany |
| |
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 :. |
| |
Keywords: | Linear languages Kleene algebra Semiring module |
本文献已被 ScienceDirect 等数据库收录! |
|