Towards Kleene algebra with recursion

From MaRDI portal





The paper deals with extending D. Kozen's theory of Kleene algebras (KA) in order to axiomatize parts of the equational theory of context-free languages, using at least fixed-point operator \(\mu\) instead of Kleene's iteration operator *. This is done in three steps: (1) The KA theory is extended to KA with idempotent semirings and least pre-fixed points for \(\mu\), called KAF theory; (2) KAF is extended by equational axioms that can model iteration by recursion, obtaining KA with recursion, KAR theory; (3) Finally, KAR theory is extended with axioms expressing the way S. Greibach eliminate left recursion in context-free grammars, obtaining KAG theory. There are considered continuous (w.r.t. Scott topology) models of KAF, and related to the Conway's notion of standard KA. It is shown that all continuous models of KAF satisfy the specific equations met in step (3). Moreover, an equation between \(\mu\)-regular expressions that is valid in the interpretation by context-free languages holds universally in the continuous models of KAF. Five open non-trivial problems are stated and discussed. For the entire collection see [Zbl 0772.68004].











This page was built for publication: Towards Kleene algebra with recursion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4202947)