Normal Forms for Elements of ${}^{\ast }$-Continuous Kleene Algebras Representing the Context-Free Languages

Abstract

Within the tensor product $K{\otimes }_{\mathcal{R}}{C}_2^{\prime }$ of any ${}^{\ast }$-continuous Kleene algebra $K$ with the polycyclic ${}^{\ast }$-continuous Kleene algebra $C_2^{\prime }$ over two bracket pairs there is a copy of the fixed-point closure of $K$: the centralizer of $C_2^{\prime }$ in $K{\otimes }_{\mathcal{R}}{C}_2^{\prime }$. Using an automata-theoretic representation of elements of $K{\otimes }_{\mathcal{R}}{C}_2^{\prime }$ Ã la Kleene, with the aid of normal form theorems that restrict the occurrences of brackets on paths through the automata, we develop a foundation for a calculus of context-free expressions without variable binders. We also give some results on the bra-ket ${}^{\ast }$-continuous Kleene algebra $C_2$, motivate the ``completeness equation'' that distinguishes $C_2$ from $C_2^{\prime }$, and show that $C_2^{\prime }$ already validates a relativized form of this equation.

final version. 42 pages, 4 figures. References sorted alphabetically