首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号