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

Within the tensor product $K{C}_2^{\mathrm{\prime }}$ of any ${}^{\ast }$-continuous Kleene algebra $K$ with the polycyclic ${}^{\ast }$-continuous Kleene algebra $C_2^{\mathrm{\prime }}$ over two bracket pairs there is a copy of the fixed-point closure of $K$: the centralizer of $C_2^{\mathrm{\prime }}$ in $K{C}_2^{\mathrm{\prime }}$. Using an automata-theoretic representation of elements of $K{C}_2^{\mathrm{\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^{\mathrm{\prime }}$, and show that $C_2^{\mathrm{\prime }}$ already validates a relativized form of this equation.