Towards Kleene algebra with recursion
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].
- Towards an algebraic theory of recursion
- From Kleene algebra to refinement algebra
- Kleene algebra with converse
- Kleene algebra with products and iteration theories
- Algorithms for Kleene algebra with converse
- Kleene algebra with hypotheses
- On Kleene algebras
- Kleene algebra with relations
- Kleene automata and recursion theory
- Relational Methods in Computer Science
- Algebraically complete semirings and Greibach normal form
- Determinization of inverted grammar programs via context-free expressions
- Kleene algebra with products and iteration theories
- Partial derivatives for context-free languages. From -regular expressions to pushdown automata
- A Quest for Kleene Algebra in 2 Dimensions
- scientific article; zbMATH DE number 3984549 (Why is no real title available?)
- scientific article; zbMATH DE number 65747 (Why is no real title available?)
- Pointer Kleene algebra
- Sequencing and intermediate acceptance: Axiomatisation and decidability of bisimilarity
- Algebraic notions of nontermination: Omega and divergence in idempotent semirings
- Bounded fixed-point definability and tabular recognition of languages
- A proof theory of right-linear ( -)grammars via cyclic proofs
- A proof theory of ( -)context-free languages, via non-wellfounded proofs
- Model checking as program verification by abstract interpretation
- Kleene modules and linear languages
- On the expressive power of Kleene algebra with domain
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)