An Algebraic Representation of the Fixed-Point Closure of *-continuous Kleene Algebras

Abstract:
The theorem of Chomsky and Schützenberger says that each context-free
language L over a finite alphabet X is the image of the intersection
of a regular language R over X+Y and the context-free Dyck-language
D over X+Y of strings with balanced brackets from Y under the
bracket-erasing homomorphism from the monoid of strings over X+Y to
that of strings over X.

Within Hopkins' algebraization of formal language theory we show that
the algebra C(X) of context-free languages over X has an isomorphic
copy in a suitable tensor product of the algebra R(X) of regular
languages over X with a quotient of R(Y) by a congruence describing
bracket matches and mismatches. It follows that all context-free
languages over X can be defined by regular(!) expressions over X+Y
where the letters of X commute with the brackets of Y, thereby
providing a substitute for a fixed-point-operator.

This generalizes the theorem of Chomsky and Schützenberger and leads
to an algebraic representation of the fixed-point closure of
*-continuous Kleene algebras.