An algebraic representation of the fixed-point closure of *-continuous Kleene algebras – A categorical Chomsky–Schützenberger theorem

Abstract

The family ${\mathcal{R}} X^*$ of regular subsets of the free monoid $X^*$ generated by a finite set X is the standard example of a ${}^*$ -continuous Kleene algebra. Likewise, the family ${\mathcal{C}} X^*$ of context-free subsets of $X^*$ is the standard example of a $\mu$ -continuous Chomsky algebra, i.e. an idempotent semiring that is closed under a well-behaved least fixed-point operator $\mu$ . For arbitrary monoids M, ${\mathcal{C}} M$ is the closure of ${\mathcal{R}}M$ as a $\mu$ -continuous Chomsky algebra, more briefly, the fixed-point closure of ${\mathcal{R}} M$ . We provide an algebraic representation of ${\mathcal{C}} M$ in a suitable product of ${\mathcal{R}} M$ with $C_2'$ , a quotient of the regular sets over an alphabet $\Delta_2$ of two pairs of bracket symbols. Namely, ${\mathcal{C}}M$ is isomorphic to the centralizer of $C_2'$ in the product of ${\mathcal{R}} M$ with $C_2'$ , i.e. the set of those elements that commute with all elements of $C_2'$ . This generalizes a well-known result of Chomsky and Schützenberger (1963, Computer Programming and Formal Systems, 118–161) and admits us to denote all context-free languages over finite sets $X\subseteq M$ by regular expressions over $X\cup\Delta_2$ interpreted in the product of ${\mathcal{R}} M$ and $C_2'$ . More generally, for any ${}^*$ -continuous Kleene algebra K the fixed-point closure of K can be represented algebraically as the centralizer of $C_2'$ in the product of K with $C_2'$ .

1. Introduction

The classical Chomsky–Schützenberger theorem of Formal Language Theory relates the set ${\mathcal{C}} X^*$ of context-free languages of the free monoid $X^*$ over the finite set X to the set ${\mathcal{R}} (X\cup\Delta_2)^*$ of regular languages over an extension of X by a set $\Delta_2 = \{b,d,p,q\}$ of two bracket pairs b,d and p,q. It says that every $L\in {\mathcal{C}} X^*$ is the image of the intersection $R\cap D_2(X)$ of a regular language $R\in{\mathcal{R}}(X\cup\Delta_2)^*$ with the Dyck language $D_2(X) \in{\mathcal{C}}(X\cup\Delta_2)^*$ of balanced bracketed strings under the homomorphism $h_{X^*}:(X\cup\Delta_2)^*\to X^*$ that keeps elements of X fixed and maps those of $\Delta_2$ to the unit of $X^*$ . This result of Chomsky and Schützenberger (1963) can be stated as

\begin{equation*}(CST)\qquad {\mathcal{C}} X^* \subseteq \left\{\,\!h_{X^*}(R\cap D_2(X))\,\mid\,R\in {\mathcal{R}} (X\cup\Delta_2)^*\!\,\right\}.\end{equation*}

Intuitively, for $L=h_{X^*}(R\cap D_2(X))$ , the set $R\cap D_2(X)$ consists of the sentences of L enriched by begin- and end-markers of their phrases according to some context-free grammar for L, i.e. by their linearized parse trees; the two bracket pairs of $\Delta_2$ are used to encode a begin- and end-marker for each phrase category of the grammar. The reverse inclusion

\begin{equation*}(\textit{reverse CST})\qquad {\mathcal{C}} X^* \supseteq \left\{\,\!h_{X^*}(R\cap D_2(X))\,\mid\,R\in {\mathcal{R}}(X\cup\Delta_2)^*\!\,\right\}\end{equation*}

is trivial, since the intersection of a context-free set with a regular one and the homomorphic image of a context-free set are context-free. (It will no longer be trivial in the generalizations considered below.) Thus, balanced brackets are at the heart of the extension from regular to context-free sets.

To extend this relation ${\mathcal{C}} X^* = \left\{\,\!h_{X^*}(R\cap D_2(X))\,\mid\,R\in{\mathcal{R}}(X\cup\Delta_2)^*\!\,\right\}$ from finitely generated free monoids $X^*$ to arbitrary monoids M, we define ${\mathcal{R}} M$ and ${\mathcal{C}} M$ as suitable closures of the semiring ${\mathcal{F}} M$ of finite subsets of M (with union as addition and elementwise product as multiplication) within the semiring ${\mathcal{P}} M$ of all subsets of M. Namely, the family ${\mathcal{C}} M$ of context-free subsets of M is the closure of ${\mathcal{F}} M$ under components of least solutions of finite systems of inequations

(1) \begin{equation} y_1 \geq p_1(y_1,\ldots,y_n), \ldots, y_n \geq p_n(y_1,\ldots,y_n)\end{equation}

between variables $y_i$ and polynomials $p_i\in {\mathcal{C}} M[y_1,\ldots,y_n]$ . Notice that each such inequation system does have a least solution in ${\mathcal{P}}M$ , so we can add the components of this solution to ${\mathcal{C}} M$ . By adding further unknowns and inequations for the coefficients from ${\mathcal{C}} M$ , we can ultimately do with polynomials $p_i\in {\mathcal{F}} M[y_1,\ldots,y_n]$ in (1). The family ${\mathcal{R}} M$ of regular sets of M is the closure of ${\mathcal{F}} M$ under components of least solutions of finite systems of inequations $y_i\geq p_i(y_1,\ldots,y_n)$ with right-linear polynomials $p_i\in{\mathcal{R}} M[y_1,\ldots,y_n]$ , i.e. where $p_i$ is a sum of monomials A or Ay with $A\in {\mathcal{R}} M$ and $y\in\{y_1,\ldots,y_n\}$ . These definitions make ${\mathcal{C}} M$ resp. ${\mathcal{R}} M$ be closed under least fixed points of arbitrary resp. right-linear polynomials and do not assume that M be finitely generated.

In classical Formal Language Theory, regular and context-free languages are defined by regular and context-free grammars. A context-free grammar $G = (X,Y,P,S)$ over the set of terminal symbols X is a finite set $P\subseteq Y\times (X\cup Y)^*$ of grammar rules or productions $(y,\alpha)$ , where Y is a set of variables or nonterminal symbols, disjoint from X, and a specific start symbol $S\in Y$ . The productions give rise to a binary rewrite relation $\Rightarrow_G$ on $(X\cup Y)^*$ by $w\Rightarrow_G w'$ iff for some $u,v\in (X\cup Y)^*$ and $(y,\alpha)\in P$ , $w=uyv$ and $w'=u\alpha v$ . Each $y\in Y$ leads to a language $L(G,y) = \left\{\,\!w\in X^*\,\mid\,y\Rightarrow^+_G w\!\,\right\}$ , where $\Rightarrow_G^+$ is the transitive closure of $\Rightarrow_G$ , and $L(G) =L(G,S)$ is the language defined by G. A right-linear grammar is a context-free grammar where $P\subseteq Y\times (X^*\cup X^*Y)$ .

Notice that P gives rise to a system (1) with $Y=\{y_1,\ldots,y_n\}$ and $S=y_1$ where $p_i$ is the sum over all monomials $\alpha'\in {\mathcal{F}} X^*[y_1,\ldots,y_n]$ that arise from the right-hand side of a grammar rule $(y_i,\alpha)$ by replacing each $x\in X$ occurring in $\alpha$ by the singleton $\{x\}\in {\mathcal{F}} X^*$ . The languages $(L(G,y_1),\ldots,L(G,y_n))$ are the least solution of the system (1) derived from G in this way. Conversely, a polynomial system (1) with parameters from ${\mathcal{F}} X^*$ gives rise to a context-free grammar $G=(X,Y,P,y_1)$ with $Y=\{y_1,\ldots,y_n\}$ and P consisting of those $(y_i,\alpha)$ where $\alpha$ arises from a monomial $\alpha'$ of $p_i$ by replacing each parameter in $\alpha'$ by one of its members $w\in X^*$ . The least solution $(L_1,\ldots,L_n)$ of the given polynomial system agrees with the languages $(L(G,y_1),\ldots,L(G,y_n))$ of the grammar so derived from it.

The grammatical way to define ${\mathcal{C}} X^*$ can be extended from free monoids $X^*$ to arbitrary monoids M, following Hopkins (2008a). The free extension M[Y] of a monoid M by a set Y disjoint from M consists of the set of all finite sequences $m_0y_1m_1\ldots y_km_k$ , where $m_0,\ldots,m_k\in M$ and $y_1,\ldots,y_k\in Y$ , with the sequence $m_0$ of length 1 with $m_0=1$ as unit, and with the operation defined by

\begin{equation*} (m_0y_1m_1\ldots y_km_k)(m_0'y_1'm_1'\ldots y_{k'}'m_{k'}') =m_0y_1m_1\ldots y_k(m_k\cdot^Mm_0')y_1'm_1'\ldots y_{k'}'m_{k'}'\end{equation*}

for $k,k'\in{\mathbb{N}}, m_0,\ldots,m'_{k'}\in M, y_1,\ldots,y_{k'}'\in Y$ as product; for disjoint sets X and Y, there is an isomorphism $X^*[Y] \simeq (X\cup Y)^*$ , obtained by identifying $y1y'\in X^*[Y]$ with $yy'\in Y^*$ . A context-free grammar $G=(Y,P,S)$ over the monoid M then consists of a set Y of variables, disjoint from M, a finite set $P\subseteq Y \times M[Y]$ of productions, and a main variable $S\in Y$ . As for free monoids, G gives rise to a binary relation $\Rightarrow_G$ on M[Y] such that $w\Rightarrow_G w'$ iff for some $\alpha,\beta \in M[Y]$ and $(y,\gamma)\in P$ , $w=\alpha y \beta$ and $w'=\alpha \gamma\beta$ . For each variable $y \in Y$ , G defines a subset $L(G,y) = \left\{\,\!m\in M\,\mid\,y\Rightarrow_G^+ m\!\,\right\}$ of M, where $\Rightarrow^+_G$ is the transitive closure of $\Rightarrow_G$ , and $L(G) := L(G,S)$ . This gives us a grammatical definition of a set

\begin{equation*}{\mathcal{C}} M = \left\{\,\!L(G)\,\mid\,G\textrm{ a context-free grammar over }M\!\,\right\}.\end{equation*}

The equivalence between the two definitions of ${\mathcal{C}} M$ can be shown by relating context-free grammars over M with finite systems of polynomial inequations with parameters from ${\mathcal{F}} M$ , as in the case of free monoids. (For an equivalence proof, see also Remark 2 in Leiß and Hopkins 2018). The regular subsets ${\mathcal{R}} M$ can be defined analogously by context-free grammars with right-linear productions. Independently of the aims of the present article, ${\mathcal{R}} M$ and ${\mathcal{C}} M$ with non-free monoid M are useful to study rational or context-free transductions T between a free input monoid $X^*$ and a free output monoid $Z^*$ as subsets of $M=X^*\times Z^*$ .

The components of least solutions in ${\mathcal{P}} X^*$ of polynomial systems (1) with right-linear polynomials $p_i\in {\mathcal{R}}X^*[y_1,\ldots, y_n]$ can be denoted by regular expressions in the elements of X. The regular expressions over X, defined by

\begin{equation*} r,s ::= 0 \mid 1 \mid x \mid (r+s) \mid (r\cdot s) \mid r^* \quad\textrm{with} x ranging over X,\end{equation*}

are interpreted in the Kleene algebra ${\mathcal{R}} X^*$ by taking $\emptyset$ for 0, the singleton containing the unit of $X^*$ for 1, $\{x\}$ for $x \in X$ , binary union for $+$ , elementwise concatenation for $\cdot$ , and iteration (aka monoid closure) for ${}^*$ . If the right-linear polynomial $p_n$ of (1) is $q(y_1,\ldots,y_{n-1})+Ay_n$ and r denotes the parameter $A\in {\mathcal{R}} X^*$ , then the least solution of $y_n \geq p_n(y_1,\ldots,y_n)$ is denoted by $(r^* \cdot q)(y_1,\ldots,y_{n-1})$ . Substituting $y_n$ by $(r^*\cdot q)$ in the remaining inequations, and iterating this process, the first component of the least solution of (1) is named by a regular expression over X, free of unknowns $y_1,\ldots,y_n$ .

In a similar way, the components of least solutions of arbitrary polynomial inequations (1) with parameters from ${\mathcal{C}} X^*$ can be named by regular $\mu$ -terms over X,

\begin{equation*} r,s ::= 0\mid 1\mid x \mid y \mid (r+s) \mid (r\cdot s) \mid r^* \mid \mu y.r, \quad\textrm{with} \, {x} \, ranging over \, {X},\end{equation*}

the extension of regular expressions over X by an infinite set of variables y and a unary least-fixed point operator $\mu$ binding a variable; then $(\mu y_n.p_n)(y_1,\ldots,y_{n-1})$ is a term denoting the least solution of $y_n\geq p_n(y_1,\ldots,y_n)$ of (1), relative to given values for $y_1,\ldots,y_n$ in ${\mathcal{C}} X^*$ . One of the results of this article is an algebraic notation for context-free languages that is close to the regular expressions and does not use a binding operator.

Now, the Chomsky–Schützenberger theorem and its reverse extend readily to the families ${\mathcal{R}} M$ of regular and ${\mathcal{C}} M$ of context-free subsets of an arbitrary finitely generated monoid M as

(2) \begin{equation} {\mathcal{C}} M = \left\{\,\!h_M(R\cap D_2(M))\,\mid\,R\in {\mathcal{R}} (M[\Delta_2])\!\,\right\}.\end{equation}

We here assume M to be finitely generated to have $D_2(M)\in {\mathcal{C}}(M[\Delta_2])$ , but this assumption can be avoided by a different formulation using the pure Dyck language $D_2\in {\mathcal{C}}\Delta_2^*$ of brackets only,

\begin{equation*}{\mathcal{C}} M = \left\{\,\!\pi_1(R\cap (M\times D_2))\,\mid\,R\in {\mathcal{R}} (M \times \Delta_2^*)\!\,\right\},\end{equation*}

where $\pi_1:M\times\Delta_2^*\to M$ is the first projection.

In a number of semi-published contributions, Hopkins (1993) has tried to turn this dependence of ${\mathcal{C}} M$ on ${\mathcal{R}}(M[\Delta_2])$ into a dependence on ${\mathcal{R}} M$ , express it in more algebraic terms, and generalize it to an algebraic construction of the fixed-point-closure of a ${}^*$ -continuous Kleene algebra K. The idea is to let elements of M and $\Delta_2$ commute with each other, i.e. replace $M[\Delta_2]$ by $M\times\Delta_2^*$ or ${\mathcal{R}}(M[\Delta_2])$ by a suitable product ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2$ of ${\mathcal{R}} M$ with a “bra-ket algebra” $C_2$ , and perform the balance-check $\cap\,D_2(M)$ and the bracket-erasure $h_M$ of (2) by algebraic calculations in $C_2$ . The “bra-ket algebra”

\begin{equation*} C_2 = {\mathcal{R}} \Delta_2^*/{\left\langle {bd = 1 = pq, bq=0=pd, db+qp=1}\right\rangle} \end{equation*}

is the quotient of the regular sets ${\mathcal{R}} \Delta_2^*$ by a congruence that is generated by three conditions ¹ : by “match” conditions $bd=1=pq$ that allow us to shorten strings by erasing all pairs bd or pq of matching adjacent brackets, by “mismatch” conditions $bq=0=pd$ that allow us to throw away all strings containing a bracket mismatch bq or pd, and by a “completeness” condition $db+qp =1$ which ensures that corresponding bra-ket algebras $C_n$ based on $n>2$ bracket pairs can be embedded in $C_2$ . ² The product ${\mathcal{R}} M \mathop{\otimes_{\mathcal{R}}} C_2$ is, intuitively, the smallest ${}^*$ -continuous Kleene algebra extension of ${\mathcal{R}} M$ and $C_2$ in which elements of ${\mathcal{R}} M$ commute with those of $C_2$ . The algebraic version of the Chomsky–Schützenberger theorem and its reverse then is that ${\mathcal{C}} M$ is isomorphic to the centralizer of $C_2$ in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}}C_2$ ,

(3) \begin{equation}{\mathcal{C}} M \simeq Z_{{C_2}}({{\mathcal{R}} M} \mathop{\otimes_{\mathcal{R}}} {C_2}),\end{equation}

i.e. to the set of elements that commute with every member of $C_2$ . All elements of ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2$ can be denoted by regular expressions in the generators of M and $C_2$ , and it is easy to define a subset of expressions that denote the members of the centralizer of $C_2$ . This is the above-mentioned algebraic notation system for context-free sets that is much closer to the familiar one for regular sets than context-free grammars or regular $\mu$ -terms are.

The goal of the present work is to replace $C_2$ in (3) by a simpler algebra, the “polycyclic ${}^*$ -continuous Kleene algebra on two generators,”

\begin{equation*} C_2' = {\mathcal{R}} \Delta_2^*/{\left\langle {bd = 1 = pq, bq=0=pd}\right\rangle}, \end{equation*}

and instead of (3) prove

(4) \begin{equation} {\mathcal{C}} M \simeq Z_{{C_2'}}({{\mathcal{R}} M} \mathop{\otimes_{\mathcal{R}}} {C_2'}),\end{equation}

our first main result. The congruence used in $C_2'$ is generated by just the bracket match and mismatch conditions. These, but not the completeness condition, can be seen as monoid equations, provided we extend $\Delta_2^*$ by an annihilating monoid element 0. Doing so gives us the “polycyclic monoid on two generators,”

\begin{equation*} P_2' = (\Delta_2\cup\{0\})^*/{\left\langle {\left\{\,x0=0=0x\,\mid\,x\in\Delta_2\cup\{0\}\!\,\right\}\cup\{bd = 1 =pq, bq = 0 = pd\}}\right\rangle}.\end{equation*}

This allows us to treat $C_2'$ as ${\mathcal{R}} P_2'$ modulo $\{0\}=\emptyset$ and ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ as ${\mathcal{R}} (M\times P_2')$ modulo $\{(1,0)\}=\emptyset$ . Moreover, it lets us understand the centralizer of $C_2'$ in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}}C_2'$ : it contains (the equivalence classes of) those $R\in {\mathcal{R}}(M\times P_2')$ where $R\subseteq M\times \{0,1\}$ .

Intuitively, therefore, (4) says that the context-free sets $L\in {\mathcal{C}} M$ correspond to the regular sets $R\in {\mathcal{R}}(M\times P_2')$ whose elements (m,t’) have $t'\in \{0,1\}$ : elements $(m,1)\in R$ come from an element $m\in M\cap L$ with a parse tree $t\in D_2\subseteq\Delta_2^*$ with respect to a context-free grammar for L, reduced to $t'=1$ in $P_2'$ ; elements $(m,0)\in R$ come from unparsable $m \in M \setminus L$ and are thrown away in the quotient of ${\mathcal{R}}(M\times P_2')$ by $\{(1,0)\} =\emptyset$ .

However, the algebraic form (4) of the Chomsky–Schützenberger theorem and its reverse for monoids does not yet give an algebraic representation of the fixed-point closure of an arbitrary ${}^*$ -continuous Kleene algebra K, which need not be of the form ${\mathcal{R}} M$ for some monoid M. Equipped with suitable notions of ${\mathcal{R}}$ - and ${\mathcal{C}}$ -morphisms, the categories of ${}^*$ -continuous Kleene algebras (Kozen 1981) and $\mu$ -continuous Chomsky algebras (Grathwohl et al. 2013), respectively, are subcategories ${\mathbb{D}}{\mathcal{R}}$ and ${\mathbb{D}}{\mathcal{C}}$ of the category ${\mathbb{D}}$ of dioids (i.e. idempotent semirings). In fact, ${\mathbb{D}}{\mathcal{R}}$ and ${\mathbb{D}}{\mathcal{C}}$ are the Eilenberg-Moore categories of certain monads on the category of monoids. The Kleene algebras ${\mathcal{R}} M$ and the Chomsky algebras ${\mathcal{C}} M$ , with monoid M, form the so-called Kleisli subcategories of ${\mathbb{D}}{\mathcal{R}}$ and ${\mathbb{D}}{\mathcal{C}}$ . We want to extend (4) from their Kleisli subcategories to the categories ${\mathbb{D}}{\mathcal{R}}$ and ${\mathbb{D}}{\mathcal{C}}$ themselves. In an equivalent categorical formulation of Hopkins (2008a) and Leiß and Hopkins (2018), the objects of ${\mathbb{D}}{\mathcal{R}}$ and ${\mathbb{D}}{\mathcal{C}}$ , called ${\mathcal{R}}$ -dioids and ${\mathcal{C}}$ -dioids there, are dioids in which the regular resp. context-free subsets U of their multiplicative monoids have least upper bounds $\sum U$ with respect to the partial order given by addition. As part of a broader program of algebraization of formal language theory, Hopkins (2008b) shows that there is an adjunction

\begin{equation*} {Q_{\mathcal{R}}^{\mathcal{C}}} : {\mathbb{D}}{\mathcal{R}} \to {\mathbb{D}}{\mathcal{C}} \quad\textrm{ and }\quad {Q_{\mathcal{C}}^{\mathcal{R}}} :{\mathbb{D}}{\mathcal{C}}\to{\mathbb{D}}{\mathcal{R}}\end{equation*}

between these categories, where ${Q_{\mathcal{C}}^{\mathcal{R}}}$ is the forgetful functor (restricting $\sum$ to regular subsets) and ${Q_{\mathcal{R}}^{\mathcal{C}}}$ maps an ${\mathcal{R}}$ -dioid K to its fixed-point- or ${\mathcal{C}}$ -closure in ${\mathbb{D}}{\mathcal{C}}$ , which extends K by a set of order-theoretic ideals of K. In yet unpublished work, Hopkins tries to show that the ${\mathcal{C}}$ -closure of an arbitrary ${\mathcal{R}}$ -dioid K can also be algebraically described as

(5) \begin{equation} {Q_{\mathcal{R}}^{\mathcal{C}}}(K) \simeq Z_{{C_2}}({K} \mathop{\otimes_{\mathcal{R}}} {C_2}).\end{equation}

Based on (4), our second main result is that, again, $C_2$ can be replaced by the simpler algebra $C_2'$ , yielding a “categorical” Chomsky–Schützenberger theorem

(6) \begin{equation} {Q_{\mathcal{R}}^{\mathcal{C}}}(K) \simeq Z_{{C_2'}}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}).\end{equation}

In contrast to the case of the Kleisli subcategories, we here really need the categorical notion of product of ${\mathcal{R}}$ -dioids. A detailed presentation of the algebraic and categorical background used here is given in Hopkins and Leiß (2018).

The rest of this paper is organized as follows. Section 2 gives the background of categories ${\mathbb{D}}{\mathcal{A}}$ of ${\mathcal{A}}$ -dioids for certain subfunctors ${\mathcal{A}}$ of the powerset functor ${\mathcal{P}} : {\mathbb{M}}\to {\mathbb{M}}_\leq$ , where ${\mathbb{M}}$ (resp. ${\mathbb{M}}_\leq$ ) is the category of (partially ordered) monoids and (monotone) homomorphisms. Section 2 also collects definitions and known results on products and quotients of ${\mathcal{A}}$ -dioids and introduces polycyclic ${\mathcal{A}}$ -dioids $C_{n,{\mathcal{A}}}'$ with n generators. Section 3 proves the algebraic version ${\mathcal{C}} M \subseteq Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ of the Chomsky–Schützenberger theorem; Section 4 the algebraic version of the reverse Chomsky–Schützenberger theorem, ${\mathcal{C}} M \supseteq Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ . These are combined in Section 5 to a proof that $Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is the ${\mathcal{C}}$ -closure of ${\mathcal{R}} M$ ; for $M=X^*$ , this leads to a set of regular expressions over $X\cup\Delta_2$ that evaluate to the context-free sets of ${\mathcal{C}} M$ . Section 6 finally proves the general representation result: for an arbitrary ${\mathcal{R}}$ -dioid K, the ${\mathcal{C}}$ -closure of K is isomorphic to $Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ . In the Conclusion, we also sketch where Hopkins’ proof of (5) uses the completeness assumption and how it is avoided in our proof of (6).

2. The Category of ${\mathcal{A}}$ -Dioids and ${\mathcal{A}}$ -Morphisms

Let ${\mathbb{M}}$ be the category of monoids $(M,\cdot,1)$ and homomorphisms between monoids, and ${\mathbb{M}}_\leq$ the category of partially ordered monoids $(M,\cdot,1,\leq)$ and monotone homomorphisms between them. We consider subfunctors of the powerset functor ${\mathcal{P}}:{\mathbb{M}}\to{\mathbb{M}}_\leq$ and partially order them by ${\mathcal{A}}\leq{\mathcal{A}}'$ iff for all monoids M, ${\mathcal{A}} M\subseteq {\mathcal{A}}'M$ . A monadic operator ³ is a functor ${\mathcal{A}}:{\mathbb{M}}\to {\mathbb{M}}_\leq$ such that for all monoids M, N,

1. ( $A_0$ ) ${\mathcal{A}} M$ is a set of subsets of M,

2. ( $A_1$ ) ${\mathcal{A}} M$ contains all singleton subsets of M,

3. ( $A_2$ ) ${\mathcal{A}} M$ is closed under products; hence, $({\mathcal{A}} M,\cdot,\{1\},\subseteq)$ is a partially ordered monoid, where

   \begin{equation*} A\cdot B := \left\{\,a\cdot b\,\mid\,a\in A,b\in B\,\right\} \quad\textrm{for }A,B\in{\mathcal{A}} M,\end{equation*}

4. ( $A_3$ ) ${\mathcal{A}} M$ is closed under unions of sets from ${\mathcal{A}}(({\mathcal{A}} M,\cdot,\{1\}))$ , and

5. ( $A_4$ ) if $f:M\to N$ is a homomorphism, so is ${\mathcal{A}} f:{\mathcal{A}} M \to {\mathcal{A}} N$ , where for $U\subseteq M$ ,

   \begin{equation*} ({\mathcal{A}} f)(U) := \left\{\,f(u)\,\mid\,u\in U\,\right\}. \end{equation*}

We write ${\mathcal{A}} M$ for both the selected set of subsets of M and the partially ordered monoid $({\mathcal{A}} M,\cdot,\{1\},\subseteq)$ or just the monoid $({\mathcal{A}} M,\cdot,\{1\})$ . For the lifting ${\mathcal{A}} f$ of f, we often write $\widetilde f$ .

An ${\mathcal{A}}$ -dioid $(D,\cdot,1,\leq)$ is a partially ordered monoid which is ${\mathcal{A}}$ -complete, i.e. each $U\in {\mathcal{A}} D$ has a least upper bound, $\sum U \in D$ , and ${\mathcal{A}}$ -distributive, i.e.

\begin{equation*} \left(\sum U\right)\left(\sum V\right) = \sum(UV) \qquad\textrm{for all }U,V\in{\mathcal{A}} D.\end{equation*}

An ${\mathcal{A}}$ -morphism $f:D \to D'$ between ${\mathcal{A}}$ -dioids D and D’ is a monotone homomorphism such that $f(\sum U)=\sum ({\mathcal{A}} f)(U)$ for all $U\in {\mathcal{A}} D$ . Let ${\mathbb{D}}{\mathcal{A}}$ be the category of ${\mathcal{A}}$ -dioids and ${\mathcal{A}}$ -morphisms between ${\mathcal{A}}$ -dioids.

Example 1 (Hopkins 2008a) The following functors are monadic operators:

1. (1). ${\mathcal{I}}$ , where ${\mathcal{I}} M$ is the set of all singleton subsets of M; ${\mathbb{D}}{\mathcal{I}}$ is the category ${\mathbb{M}}$ of monoids (with equality as partial order) and (monoid-) homomorphisms.

2. (2). ${\mathcal{F}}$ , where ${\mathcal{F}} M$ is the set of all finite subsets of M; ${\mathbb{D}}{\mathcal{F}}$ is the category ${\mathbb{D}}$ of dioids and dioid homomorphisms.

3. (3). ${\mathcal{R}}$ , where ${\mathcal{R}} M$ is the set of all regular subsets of M; ${\mathbb{D}}{\mathcal{R}}$ is the category of ${}^*$ -continuous Kleene algebras and morphisms between them, see Kozen (1981), Hopkins (2008a).

4. (4). ${\mathcal{C}}$ , where ${\mathcal{C}} M$ is the set of all context-free subsets of M; ${\mathbb{D}}{\mathcal{C}}$ is the category of $\mu$ -continuous Chomsky algebras and morphisms between them, see Grathwohl et al. (2013), Leiß and Hopkins (2018).

5. (5). ${\mathcal{T}}$ , where ${\mathcal{T}} M$ is the set of all Turing-subsets (r.e.) of M. Notice that ( $A_3$ ) generalizes the well-known fact that the union of an r.e. family of r.e. subsets of ${\mathbb{N}}$ is an r.e. subset of ${\mathbb{N}}$ .

6. (6). ${\mathcal{P}}_{\aleph_0}$ , where ${\mathcal{P}}_{\aleph_0} M$ is the set of countable subsets of M; ${\mathbb{D}}{\mathcal{P}}_{\aleph_0}$ is the category of closed semirings, see Kozen (1990).

7. (7). ${\mathcal{P}}$ , the power set operator; ${\mathbb{D}}{\mathcal{P}}$ is the category of quantales with unit (Rosenthal 1990).

The sets ${\mathcal{R}} M$ , ${\mathcal{C}} M$ , ${\mathcal{T}} M$ can be defined by generalizing the grammatical approach of doing so for free monoids $M=X^*$ (Hopkins 2008a). We use the more algebraic, equivalent definitions for ${\mathcal{R}}$ and ${\mathcal{C}}$ given in Hopkins and Leiß (2018). ${\mathcal{R}} M$ is the closure of ${\mathcal{F}} M$ under (binary) union, elementwise product, and iteration ${}^*$ , i.e. if $A\in {\mathcal{R}} M$ , so is $A^* := \bigcup\left\{\,A^n\,\mid\,n\in{\mathbb{N}}\,\right\}$ , where $A^0=\{1\}$ , $A^{n+1}= A^n\cdot A$ . ${\mathcal{C}} M$ is the closure of ${\mathcal{F}} M$ under components of least solutions of polynomial systems over ${\mathcal{C}} M$ , i.e. the components $A_1,\ldots,A_n$ of the least solution in ${\mathcal{P}} M$ of a system of inequations

\begin{equation*} x_1\geq p_1(x_1,\ldots,x_n),\ \ldots,\ x_n\geq p_n(x_1,\ldots,x_n) \end{equation*}

with polynomials $p_i$ in $x_1,\ldots,x_n$ with parameters from ${\mathcal{C}} M$ all belong to ${\mathcal{C}} M$ . $\diamond$

A Kleene Algebra $(K,+,\cdot,{}^*,0,1)$ is an idempotent semiring with a unary operation ${}^*$ such that $a^*b$ is the least solution x of $ax+b\leq x$ and $ba^*$ the least solution of $xa+b\leq x$ , where $y \leq z$ is defined by $y+z=z$ (Kozen 1994). The Kleene algebra K is ${}^*$ -continuous if

\begin{equation*} ac^*b = \sum\!\left\{\,\!ac^mb\,\mid\,m\in{\mathbb{N}}\!\,\right\} \qquad\textrm{for all $a,b,c \in K$}. \end{equation*}

A Chomsky algebra (Grathwohl et al. 2013) is an idempotent semiring K that is algebraically closed, i.e. where every finite system of inequations $x_1\geq p_1(x_1,\ldots,x_n),\ldots,x_n\geq p_n(x_1,\ldots,x_n)$ with polynomials $p_i\in K[x_1,\ldots,x_n]$ has a least solution $a_1,\ldots,a_n\in K$ . If semiring terms, i.e. terms in $0,1,+,\cdot$ , are extended to $\mu$ -terms by adding a unary fixed-point operator $\mu$ , the least solution of $x\geq p(x,x_1,\ldots,x_k)$ can be named by the term $(\mu x.p)(x_1,\ldots,x_k)$ . A Chomsky algebra is $\mu$ -continuous, if for all $\mu$ -terms $\mu x.p$ with parameters from K,

\begin{equation*} a(\mu x.p)b = \sum\!\left\{\,\!a\cdot p^m(0)\cdot b\,\mid\,m\in{\mathbb{N}}\!\,\right\} \qquad\textrm{for all $a,b \in K$}.\end{equation*}

In the ${}^*$ - and $\mu$ -continuity conditions, the existence of the least upper bounds on the right is asserted, not assumed. Hence, these conditions are related to the ${\mathcal{R}}$ - and ${\mathcal{C}}$ -dioid axioms by the existence assertions $U=\left\{\,c^m\,\mid\,m\in{\mathbb{N}}\,\right\}\in{\mathcal{R}} K$ resp. $U=\left\{\,p^m(0)\,\mid\,m\in{\mathbb{N}}\,\right\} \in {\mathcal{C}}K$ and the ${\mathcal{A}}$ -distributivity assertion, for ${\mathcal{A}} = {\mathcal{R}}$ resp. ${\mathcal{A}}={\mathcal{C}}$ ,

\begin{equation*} a\left(\sum U\right)b = \sum aUb, \quad\textrm{ for all }a,b\in K, \end{equation*}

which (assuming ${\mathcal{A}}$ -completeness) is equivalent to the ${\mathcal{A}}$ -distributivity condition above. Of course, by ${\mathcal{A}} K$ we mean ${\mathcal{A}}$ applied to the multiplicative monoid of K. We refer to Hopkins (2008a) and Leiß and Hopkins (2018) for the details of the equivalence between ${}^*$ -continuous Kleene algebras and ${\mathcal{R}}$ -dioids and between $\mu$ -continuous Chomsky algebras and ${\mathcal{C}}$ -dioids, respectively, and use the latter terminology in the following.

A dioid $(D,+,\cdot,0,1)$ is an idempotent semiring. Idempotency of $+$ provides a partial order $\leq$ on D, via $d\leq d'$ iff $d+d'=d'$ , with 0 as least element. Distributivity makes $\cdot$ monotone with respect to $\leq$ , and $+$ guarantees a least upper bound $\sum U =d_1+\ldots +d_n$ for each finite subset $U=\{d_1,\ldots,d_n\}$ of D. Let ${\mathbb{D}}$ be the category of dioids with dioid homomorphisms.

For ${\mathcal{F}}\leq {\mathcal{A}}$ , ( $A_3$ ) implies that ${\mathcal{A}} M$ is an idempotent semiring with

\begin{equation*} 0 := \bigcup\emptyset, \qquad A+B := \bigcup\{A,B\}, \quad\textrm{for }A,B\in{\mathcal{A}} M.\end{equation*}

In this case, every ${\mathcal{A}}$ -dioid $(D,\cdot,1,\leq)$ becomes a dioid $(D,+,\cdot,0,1)$ , using $a+b := \sum\{a,b\}$ and $0:=\sum\emptyset$ , and every ${\mathcal{A}}$ -morphism is a dioid homomorphism. Hence, we then view ${\mathbb{D}}{\mathcal{A}}$ as a subcategory of ${\mathbb{D}}$ .

Let us collect a number of results of that will be frequently used below:

Theorem 1 (Hopkins 2008a) Let ${\mathcal{A}}$ be a monadic operator with ${\mathcal{F}}\leq{\mathcal{A}}$ . Let M,N be monoids and D be an ${\mathcal{A}}$ -dioid.

1. (1). ${\mathcal{A}} M$ is an ${\mathcal{A}}$ -dioid.

2. (2). ${\mathcal{A}} M$ is the free ${\mathcal{A}}$ -dioid extension of M. (i.e., any homomorphism $f:M\to D$ to an ${\mathcal{A}}$ -dioid D extends uniquely to an ${\mathcal{A}}$ -morphism $f^*:{\mathcal{A}} M\to D$ such that $f(m)=f^*(\{m\})$ .)

3. (3). The least upper bound operator $\sum:{\mathcal{A}} D\to D$ is an ${\mathcal{A}}$ -morphism.

4. (4). If $f:M\to N$ is a homomorphism, its lifting ${\mathcal{A}} f:{\mathcal{A}} M\to {\mathcal{A}} N$ is an ${\mathcal{A}}$ -morphism.

5. (5). If $f:M\to N$ is a surjective homomorphism, so is its lifting ${\mathcal{A}} f:{\mathcal{A}} M\to {\mathcal{A}} N$ .

6. (6). If M is a submonoid of N, then ${\mathcal{A}} M\subseteq {\mathcal{A}} N$ .

In fact, by Theorem 16 of Hopkins (2008b), ${\mathcal{A}}:{\mathbb{M}}\to{\mathbb{D}}{\mathcal{A}}$ and the forgetful functor $\,\widehat{\!{\mathcal{A}}}:{\mathbb{D}}{\mathcal{A}}\to{\mathbb{M}}$ form an adjunction and combine to a monad $T_{\mathcal{A}}=(\widehat{\!{\mathcal{A}}}\circ{\mathcal{A}},\eta,\mu):{\mathbb{M}}\to{\mathbb{M}}$ with $m\in M \mapsto \{m\}\in{\mathcal{A}} M$ as unit $\eta$ and $U \in {\mathcal{A}}{\mathcal{A}} M\mapsto\bigcup U\in{\mathcal{A}} M$ as product $\mu$ . Therefore, ${\mathcal{A}}$ -dioids are best viewed as Eilenberg-Moore T-algebras for this monad $T_{\mathcal{A}}$ , i.e. two-sorted structures

\begin{equation*} D = \left(D,\cdot,1, \sum: {\mathcal{A}} D \to D\right) \end{equation*}

with $\sum$ as “structure map” (see Mac Lane 1971). The free ${\mathcal{A}}$ -dioids ${\mathcal{A}} M$ with monoid M are the objects of the Kleisli-category of this monad $T_{\mathcal{A}}$ .

Besides the free ${\mathcal{A}}$ -dioid extensions ${\mathcal{A}} M$ of monoids M, further examples of ${\mathcal{A}}$ -dioids can be obtained from given ones by suitable quotient and tensor product constructions as defined later. Some categories ${\mathbb{D}}{\mathcal{A}}$ are closed under matrix semiring formation, in particular:

Example 2. Let J be a non-empty set and $D=(D,+^D,\cdot^D,0^D,1^D)$ a ${\mathcal{P}}$ -dioid. Then,

\begin{equation*} {{\textit Mat}_{J,J}(D)} = \left\langle D^{J\times J},+,\cdot,0,1\right\rangle \end{equation*}

is a ${\mathcal{P}}$ -dioid, where $D^{J\times J}$ is the set of functions from $J\times J$ to D, 0 is the constant function with value $0^D$ , 1 the function with $1(i,i) = 1^D$ and $1(i,j)=0^D$ for $i\not=j$ , and $+$ and $\cdot$ are given by $(f+g)(i,j) =f(i,j)+^D g(i,j)$ and $(f\cdot g)(i,j) = \sum\left\{\,f(i,k)\cdot^D g(k,j)\,\mid\,k\in J\,\right\}$ , for all $i,j\in J$ .

${{\textit Mat}_{J,J}(D)}$ is ${\mathcal{P}}$ -complete, because any $U\subseteq {{\textit Mat}_{J,J}(D)}$ has a least upper bound $\sum U$ defined componentwise by $(\sum U)(i,j) =\sum\!\left\{\,f(i,j)\,\mid\,f\in U\,\right\}$ using $\sum:{\mathcal{P}} D\to D$ ; the ${\mathcal{P}}$ -distributivity of ${{\textit Mat}_{J,J}(D)}$ follows from the definition of matrix product and the ${\mathcal{P}}$ -distributivity of D:

\begin{eqnarray*} \left(g\cdot \left(\sum U\right)\cdot h\right)(i,j) &=& \sum\!\left\{\,\!g(i,k)\cdot^D \left(\sum\left\{\,f(k,l)\,\mid\,f\in U\,\right\}\right)\cdot^D h(l,j)\,\mid\,k,l\in J\!\,\right\} \\ &=& \sum\!\left\{\,\!g(i,k)\cdot^D f(k,l)\cdot^D h(l,j)\,\mid\,f\in U, k,l\in J\!\,\right\} \\ &=& \sum\!\left\{\,\!(g\cdot f\cdot h)(i,j)\,\mid\,f\in U\!\,\right\}.\end{eqnarray*}

Elements of ${{\textit Mat}_{J,J}(D)}$ will be called $J\times J$ -matrices over D and often are denoted by A,B; as usual, we write $A_{i,j}$ instead of A(i,j) etc. If M is a monoid, ${{\textit Mat}_{J,J}({{\mathcal{P}} M})}$ is a ${\mathcal{P}}$ -dioid. In particular, since ${\mathbb{B}} \simeq {{\mathcal{P}} M}$ for the trivial monoid M, the boolean matrices ${{\textit Mat}_{J,J}({\mathbb{B}})}$ form a ${\mathcal{P}}$ -dioid. We identify ${{\textit Mat}_{J,J}({\mathbb{B}})}$ with the ${\mathcal{P}}$ -dioid of binary relations on J and often write $(i,j) \in A\subseteq J \times J$ instead of $A_{i,j}=1$ . $\diamond$

Remark 2. Similarly, ${\mathbb{D}}{\mathcal{F}}$ is closed under ${\textit Mat}_{n,n}(\cdot)$ for finite n and ${\mathbb{D}}{\mathcal{P}}_{\aleph_0}$ under ${\textit Mat}_{J,J}(\cdot)$ for countable J. It is an open question whether ${\textit Mat}_{n,n}(D)$ is an ${\mathcal{A}}$ -dioid for an arbitrary monadic operator ${\mathcal{A}}$ and ${\mathcal{A}}$ -dioid D. The least upper bound $\sum U$ of a set $U\subseteq {\textit Mat}_{n,n}(D)$ has to satisfy $(\sum U)_{i,j} =\sum\!\left\{\,\!A_{i,j}\,\mid\,A\in U\!\,\right\}$ , but $U\in{\mathcal{A}}({\textit Mat}_{n,n}(D))$ does not seem to imply $\left\{\,\!A_{i,j}\,\mid\,A\in U\!\,\right\}\in{\mathcal{A}} D$ , so it is already unclear if the componentwise suprema exist and ${\textit Mat}_{n,n}(D)$ is ${\mathcal{A}}$ -complete. Defining the iteration $A^*$ of a matrix A of dimension $n\times n$ by a formula of Conway (1971), Kozen (1994) shows that for a Kleene algebra K, ${\textit Mat}_{n,n}(K)$ is a Kleene algebra and extends this to ${}^*$ -continuous Kleene algebras in Kozen (1991), Chapter 7.1. So the category of ${\mathcal{R}}$ -dioids is closed under ${\textit Mat}_{n,n}(\cdot)$ . Leiß (2016) shows that the category of ${\mathcal{C}}$ -dioids is closed under ${\textit Mat}_{n,n}(\cdot)$ .

Lemma 3. Let $f:M\to D$ be a homomorphism from a monoid M to a dioid D. Suppose that for each $L\in {\mathcal{A}} M$ , its image $({\mathcal{A}} f)(L)\in{\mathcal{A}} D$ has a least upper bound in D, $\widehat{\,L\,} := \sum\left\{\,f(m)\,\mid\,m\in L\,\right\}$ and that $\,\widehat{\,\cdot\,} : {\mathcal{A}} M\to D$ is a surjective homomorphism. Then, D is an ${\mathcal{A}}$ -dioid.

Proof. By Theorem 1, the map ${\mathcal{A}}(\widehat{\,\cdot\,}):{\mathcal{A}}{\mathcal{A}} M\to {\mathcal{A}} D$ is a surjective homomorphism. Therefore, we can define a least upper bound operator $\sum$ that makes the following diagram commute:

For each $V\in{\mathcal{A}} D,$ there is $U\in {\mathcal{A}}{\mathcal{A}} M$ such that $V=\left\{\,\widehat{\,L\,}\,\mid\,L\in U\,\right\}$ . Since $\bigcup U\in {\mathcal{A}} M$ , its image under $({\mathcal{A}} f)=\widetilde f$ has by assumption a least upper bound, $\widehat{\bigcup U} = \sum\left\{\,f(m)\,\mid\,m\in\bigcup U\,\right\}\in D$ . Then,

\begin{equation*} \sum V := \widehat{\bigcup U} \end{equation*}

is an upper bound of V in D, since for each $L\in U$ , $L\subseteq \bigcup U$ ; hence, $\widetilde f(L)\subseteq \widetilde f(\bigcup U)$ and $\widehat{\,L\,}\leq\widehat{\bigcup U}$ . If $e\in D$ is any upper bound of V, then for each $m\in\bigcup U$ there is $L\in U$ with $m\in L$ , so

\begin{equation*} f(m) \leq \widehat{\,L\,} \leq e. \end{equation*}

Hence, e is an upper bound of $\left\{\,f(m)\,\mid\,m\in\bigcup U\,\right\}$ and so $\widehat{\bigcup U}\leq e$ . Therefore, $\sum V$ is the least upper bound of V in D, and D is ${\mathcal{A}}$ -complete.

To show that D is ${\mathcal{A}}$ -distributive, suppose $V_1,V_2\in{\mathcal{A}} D$ . Since ${\mathcal{A}}(\widehat{\,\cdot\,}) : {\mathcal{A}}{\mathcal{A}} M\to {\mathcal{A}} D$ is surjective, there are $U_1,U_2\in {\mathcal{A}}{\mathcal{A}} M$ such that $V_i =\left\{\,\widehat{\,L\,}\,\mid\,L\in U_i\,\right\}$ and $\sum V_i = \widehat{\bigcup U_i}$ for $i=1,2$ . Then, $V_1V_2\in {\mathcal{A}} D$ has a least upper bound $\sum (V_1V_2)$ , and since $(\sum{V_1})(\sum{V_2})$ is an upper bound of $V_1V_2$ , we have $\sum(V_1V_2)\leq(\sum{V_1})(\sum{V_2})$ . For the reverse inequation, use that $\widehat{\,\cdot\,}$ and $\bigcup$ are homomorphisms:

\begin{eqnarray*} \sum(V_1V_2) &=& \sum\left\{\,\widehat{L_1}\widehat{L_2}\,\mid\,L_1\in U_1, L_2\in U_2\,\right\}\\ &=& \sum\left\{\,\widehat{L_1L_2}\,\mid\,L_1\in U_1, L_2\in U_2\,\right\}\\ &=& \sum\left\{\,\widehat{\,L\,}\,\mid\,L \in U_1U_2\,\right\}\\ &=& \sum\left\{\,\sum\left\{\,f(m)\,\mid\,m\in L\,\right\}\,\mid\,L \in U_1U_2\,\right\}\\ &\geq& \sum\left\{\,f(m)\,\mid\,m\in \bigcup(U_1U_2)\,\right\}\\ &=& \widehat{\bigcup(U_1U_2)}\\ &=& \left(\bigcup U_1\cdot\bigcup U_2\right)^{\widehat{\quad}}\\ &=& \widehat{\bigcup U_1}\cdot \widehat{\bigcup U_2}\\ &=& \left(\sum V_1\right)\left(\sum V_2\right). \\[-28pt]\end{eqnarray*}

For monadic operators ${\mathcal{A}}\leq {\mathcal{B}}$ , the ${\mathcal{B}}$ -completion of an ${\mathcal{A}}$ -dioid D is a ${\mathcal{B}}$ -dioid $\overline D$ together with an embedding ${\mathcal{A}}$ -morphism $\eta_D:D\to \overline D$ such that the following “universal property” holds: any ${\mathcal{A}}$ -morphism f from D to a ${\mathcal{B}}$ -dioid D’ extends uniquely to a ${\mathcal{B}}$ -morphism $\bar f : \overline D \to D'$ , in the sense that $f=\bar f\circ \eta_D$ :

By the universal property, the ${\mathcal{B}}$ -completion of D is unique up to a ${\mathcal{B}}$ -isomorphism.

The ${\mathcal{C}}$ -completion of a Kleene algebra or an ${\mathcal{R}}$ -dioid is analogous to the algebraic closure of a field, but instead of adjoining roots to polynomials, we adjoin least fixed points. The ${\mathcal{C}}$ -completion shall therefore also be called the ${\mathcal{C}}$ -closure or fixed-point closure of the Kleene algebra.

Proposition 4. For monoids M, the ${\mathcal{C}}$ -completion of ${\mathcal{R}} M$ is ${\mathcal{C}} M$ with the inclusion as $\eta_{{\mathcal{R}} M}$ .

Proof. ${\mathcal{C}} M$ is a ${\mathcal{C}}$ -dioid by Theorem 1 of Hopkins (2008a). If $f:{\mathcal{R}} M\to C$ is an ${\mathcal{R}}$ -morphism to a ${\mathcal{C}}$ -dioid C, we define $\bar f:{\mathcal{C}} M\to C$ by

\begin{equation*} \bar f(L) = \sum\left\{\,f(\{m\})\,\mid\,m\in L\,\right\}, \quad \textrm{ for } L\in {\mathcal{C}} M. \end{equation*}

It is routine to check that $\bar f$ is the only ${\mathcal{C}}$ -morphism $h:{\mathcal{C}}M\to C$ with $f=h\circ \eta_{{\mathcal{R}} M}$ .

In the rest of this paper, we give an algebraic construction of the ${\mathcal{C}}$ -closure ${\mathcal{C}} M$ of ${\mathcal{R}} M$ for monoids M and generalize this to a construction of the ${\mathcal{C}}$ -closure of an arbitrary ${\mathcal{R}}$ -dioid K.

2.1 Quotients in ${\mathbb{D}}{\mathcal{A}}$

From now on, we assume ${\mathcal{F}}\leq {\mathcal{A}}$ , so that all ${\mathcal{A}}$ -dioids are dioids. For a partial order $(D,\leq)$ , the down-closure of $U\subseteq D$ is $U^{\downarrow} := \left\{\,d\in D\,\mid\,d\leq u \textrm{ for some }u \in U\,\right\}$ .

If $D = (D,+^D,\cdot^D,0^D,1^D)$ is a dioid and $\rho$ a dioid-congruence on D, then $D/\rho$ , the set of congruence classes of $\rho$ , is a dioid under the operations

\begin{equation*} d/\rho + d'/\rho := (d+^Dd')/\rho, \quad d/\rho \cdot d'/\rho := (d\cdot^Dd')/\rho, \quad 0 := 0^D/\rho, \quad 1 := 1^D/\rho.\end{equation*}

The partial order $\leq$ on $D/\rho$ derived from $+$ is

\begin{equation*} d/\rho \leq d'/\rho :\iff (d+^Dd')/\rho = d'/\rho. \end{equation*}

An ${\mathcal{A}}$ -congruence on an ${\mathcal{A}}$ -dioid D is a dioid-congruence $\rho$ on D such that for all $U,U'\in {\mathcal{A}} D$ , if $(U/\rho)^{\downarrow} =(U'/\rho)^{\downarrow}$ , then $(\sum U)/\rho = (\sum U')/\rho$ .

Proposition 5 (Hopkins and Leiß 2018) If D is an ${\mathcal{A}}$ -dioid and $\rho$ an ${\mathcal{A}}$ -congruence on D, then $D/\rho$ is an ${\mathcal{A}}$ -dioid and the canonical map $d \mapsto d/\rho$ is an ${\mathcal{A}}$ -morphism.

Proof. For each $V\in {\mathcal{A}}(D/\rho)$ , there is $U\in{\mathcal{A}} D$ such that $V=U/\rho = \left\{\,d/\rho\,\mid\,d\in U\,\right\}$ . Since $\rho$ is an ${\mathcal{A}}$ -congruence, $\sum (U/\rho) := (\sum U)/\rho$ is well-defined and a least upper bound of V. (This needs ${\mathcal{F}}\leq{\mathcal{A}}$ .)

If D is an ${\mathcal{A}}$ -dioid and $E\subseteq D\times D$ , there is a least ${\mathcal{A}}$ -dioid-congruence $\rho$ on D with $E\subseteq \rho$ , the intersection of all ${\mathcal{A}}$ -dioid-congruences on D above E.

The ${\mathcal{A}}$ -dioid ${\mathcal{A}}(X^*/\rho)$ of the quotient monoid $X^*/\rho$ is isomorphic to the quotient ${\mathcal{A}} X^*/\tilde\rho$ of the free ${\mathcal{A}}$ -dioid ${\mathcal{A}} X^*$ by a suitable ${\mathcal{A}}$ -congruence $\tilde\rho$ . If $\rho$ is determined by a set E of monoid equations, $\tilde\rho$ is determined by the corresponding set of dioid equations between singleton sets:

Proposition 6 (Hopkins and Leiß 2018) Let $\rho$ be a congruence on the monoid M and ${\mathcal{A}}\rho$ the least ${\mathcal{A}}$ -congruence on ${\mathcal{A}} M$ above $\left\{\,(\{m\},\{m'\})\,\mid\,(m,m')\in \rho\,\right\}$ . Then ${\mathcal{A}}(M/\rho)\simeq {\mathcal{A}} M/{\mathcal{A}}\rho$ .

It is shown in Hopkins and Leiß (2018) that ${\mathbb{D}}{\mathcal{A}}$ has coequalizers, and the quotient $D/\rho$ of an ${\mathcal{A}}$ -dioid D by an ${\mathcal{A}}$ -congruence $\rho$ on D is the coequalizer of two suitable ${\mathcal{A}}$ -morphisms $f,g:N\rightrightarrows D$ . The kernel $\ker(f)$ of an ${\mathcal{A}}$ -morphism $f:D\to D'$ between ${\mathcal{A}}$ -dioids is an ${\mathcal{A}}$ -congruence on D.

2.2 The polycyclic ${\mathcal{A}}$ -dioids $C_{n,{\mathcal{A}}}'$

Let $\Delta_n=\{p_0,\ldots,p_{n-1},q_0,\ldots,q_{n-1}\}$ be a set of n pairs of “brackets,” $p_0,q_0$ , …, $p_{n-1},q_{n-1}$ . We decompose $\Delta_n = P_n\cup Q_n$ into the set $P_n=\left\{\,p_i\,\mid\,i<n\,\right\}$ of “opening” brackets and the set $Q_n=\left\{\,\!q_i\,\mid\,i<n\!\,\right\}$ of “closing” brackets. We also use ${\langle{i}\!\mid}$ for $p_i$ and ${\mid\!{i}\rangle}$ for $q_i$ .

Let ${\mathcal{A}}$ be a monadic operator such that $\emptyset\in{\mathcal{A}} M$ for each monoid M. The polycyclic ${\mathcal{A}}$ -dioid $C_{n,{\mathcal{A}}}'$ is the quotient $C_{n,{\mathcal{A}}}' = {\mathcal{A}}\Delta_n^*/\rho_n$ of ${\mathcal{A}}\Delta_n^*$ by the ${\mathcal{A}}$ -congruence $\rho_n$ generated by the relations

(7) \begin{equation} p_iq_j = \delta_{i,j}\quad\textrm{ for }i,j<n,\end{equation}

where $\delta_{i,j}$ is the Kronecker $\delta$ . These equations allow us to algebraically distinguish matching brackets, where $p_iq_j=1$ , from non-matching ones, where $p_iq_j=0$ . Recall that in ${\mathcal{A}} \Delta^*_n$ , elements of $\Delta_n^*$ are interpreted by their singleton sets, 0 by the empty set, so that $\rho_n$ is the least ${\mathcal{A}}$ -congruence containing $(\{p_iq_i\},\{1\})$ and $(\{p_iq_j\},\emptyset)$ for $i,j<n, i\not=j$ . The bra-ket algebra $C_{n,{\mathcal{A}}}$ of Hopkins (2007) further assumes a “completeness” condition, $1 =\sum\left\{\,q_ip_i\,\mid\,i<n\,\right\}$ , i.e.

\begin{equation*} C_{n,{\mathcal{A}}} = {\mathcal{A}}\Delta_n^*/{\left\langle {\left\{\,p_iq_j=\delta_{i,j}\,\mid\,i,j<n\,\right\}\cup\left\{1 = \sum\left\{\,q_ip_i\,\mid\,i<n\,\right\}\right\}}\right\rangle}.\end{equation*}

We will only use the case ${\mathcal{A}} ={\mathcal{R}}$ and abbreviate $C_{n,{\mathcal{R}}}$ and $C_{n,{\mathcal{R}}}'$ by $C_n$ and $C_n'$ , respectively.

Remark 7. The reason to call $1 = q_0p_0+\ldots + q_{n-1}p_{n-1}$ the completeness condition is as follows. A map $c:\{0,\ldots,n-1\}\to \{0,1\}^*$ is a prefix code if none of the code words $c_0,\ldots,c_{n-1}$ is a prefix of another one. A prefix code c is complete if for each $w\in \{0,1\}^*$ , either none or both successors w0, w1 of w are prefixes of code words. By induction on the word length, define $p_w,q_w\in\Delta_2^*$ by $p_\varepsilon = \varepsilon =q_\varepsilon$ , $p_{iw}= p_wp_i$ and $q_{iw} = q_iq_w$ for $i<2$ . Then, the map c is a prefix code iff in $C_2$ , $p_{c_i}q_{c_j} = \delta_{i,j}$ for all $i,j<n$ , and a complete prefix code iff additionally $\sum_{i<n}q_{c_i}p_{c_i} = 1$ . In the latter case, $p_i\mapsto p_{c_i}$ , $q_i\mapsto q_{c_i}$ ( $i<n$ ) is an embedding of $C_n$ into $C_2$ , for $n\geq 2$ . For example, $c_0 = 0$ , $c_1= 10$ , $c_2=11$ is a complete prefix code $c:\{0,1,2\} \to \{0,1\}^*$ , leading to an embedding of $C_3$ into $C_2$ by mapping $p_0,p_1,p_2$ to $p_0, p_0p_1, p_1p_1$ and $q_0,q_1,q_2$ to $q_0,q_1q_0,q_1q_1$ . The code words of different closing brackets are not prefixes of each other, those of different opening brackets are not suffixes of another.

As we omit the completeness condition, we can view the semiring equations (7) as monoid equations, interpreted in monoids with an annihilating element 0, which leads to a different representation of $C_{n,{\mathcal{A}}}'$ that will be useful later.

The polycyclic monoid generated by $P_n$ is the quotient $P_n' := (\Delta_n\cup\{0\})^*/\rho_n$ , where $\rho_n$ now is the monoid congruence generated by

\begin{equation*} \left\{\,p_iq_j=\delta_{i,j}\,\mid\,i,j<n\,\right\}\cup \left\{\,x0=0=0x\,\mid\,x\in \Delta_n\cup\{0\}\,\right\}.\end{equation*}

Every string $w\in (\Delta_n\cup\{0\})^*$ can be reduced to a “normal form” $\textit{nf}_{n}(w)$ , using the equations generating $\rho_n$ as rules to shorten a string. The reduction either runs into a bracket mismatch and returns 0, or finds matching brackets only and returns 1, or ends in a string with all closing brackets in front of all opening brackets. Hence, we can identify $P_n'$ with $(Q_n^*P_n^*\cup\{0\},\cdot,1)$ , where

\begin{equation*} u\cdot v := \textit{nf}_{n}(uv), \qquad u,v\in Q_n^*P_n^*\cup\{0\}. \end{equation*}

The Cayley graph of the polycyclic monoid $P_n'$ is the graph whose nodes are the elements $x\in P_n'$ with edges $x{\,\stackrel{\delta}{\longrightarrow}\,} x\cdot\delta$ , for $\delta\in \Delta_n$ .

Example 3. A drawing of a part of the Cayley graph of $P_2'$ is given in Figure 1, not showing the sink node 0 and edges connected to it. For example, there is no edge $q_0{\,\stackrel{{p_0}}{\longrightarrow}\,}1$ since $q_0p_0\not=1$ . As the picture indicates, the subgraph with nodes in $P_2^*$ corresponds to a stack $P_2^*\simeq \{0,1\}^*$ , with $p_i$ for $\textit{push}(i)$ and $q_i$ for $\textit{pop}(i)$ . ⁴ For $u\in\Delta_2^*$ , an equation $u=1$ holds in $P_2'$ iff u is the label of a path in the Cayley graph starting and ending in the node 1. The set of all those u is of course the pure Dyck language $D_2\in {\mathcal{C}} \Delta_2^*$ of balanced strings over $\Delta_2$ , i.e. the least solution in ${\mathcal{P}}\Delta_2^*$ of

\begin{equation*} y \geq 1 + p_0 y q_0 + p_1 y q_1 + yy. \end{equation*}

It is easy to define a pushdown automaton accepting $\left\{\,u\in\Delta_2^*\,\mid\,u=1 \textrm{ in }P_2'\,\right\}$ , keeping on its stack the $\rho$ -normal form of the input sequence read. $\diamond$

Figure 1. Part of the Cayley graph of $P_2'$ .

Nivat and Perrot (1970) initiated the study of the connection between polycyclic monoids and formal languages.

Remark 8. The polycyclic dioid $C_n'$ has an interpretation in the algebra of binary relations on the Cayley graph of $P_n'$ , arising from the interpretation of $p_i$ and $q_i$ as the transition relations ${\,\stackrel{{p_i}}{\longrightarrow}\,}$ and ${\,\stackrel{{q_i}}{\longrightarrow}\,}$ shown in the graph. Under this interpretation, the completeness condition $1= \sum_{i<n} q_ip_i$ is not valid, as node 1 is not related to itself by any of the relations ${\,\stackrel{q_ip_i}{\longrightarrow}\,}$ . We will later use a restriction of this interpretation to the “stack part” $P_n^*$ of $P_n'$ . It may seem that a constant $\pi$ representing an “empty stack” test is needed to model a stack properly by

\begin{equation*} 1=\pi + \sum{\left\{\,q_ip_i\,\mid\,i<n\,\right\}},\quad \pi\pi=\pi,\quad \bigwedge_{i<n}(\pi q_i=0=p_i\pi).\end{equation*}

But in our case, this turns out to be unnecessary, since computations popping from the empty stack can be interpreted by the empty transition relation (cf. the proof of Theorem 17).

The map from $P_n'$ to ${\mathcal{A}}\Delta_n^*$ given by $0 \mapsto \emptyset$ , $1\mapsto\{1\}$ , and $p_i\mapsto\{p_i\}$ , $q_i \mapsto \{q_i\}$ for $i<n$ , extends to a homomorphism from $P_n'$ to the multiplicative monoid of $C_{n,{\mathcal{A}}}'$ . Since $P_n'$ has no non-trivial congruences (by Nivat and Perrot 1970), this is an embedding of $P_n'$ into $C_{n,{\mathcal{A}}}'$ , for ${\mathcal{F}}\leq{\mathcal{A}}$ .

In the original definition $C_n' = {\mathcal{R}} \Delta_n^*/\rho_n$ , we take the quotient of the regular sets ${\mathcal{R}}\Delta_n^*$ under the semiring congruence $\rho_n$ , where 1 stands for $\{1\}$ and 0 for $\emptyset$ . We now take the regular sets ${\mathcal{R}} P_n'$ of $P_n'$ and remove the annihilating element:

Proposition 9. If $\nu$ is the least ${\mathcal{R}}$ -congruence on ${\mathcal{R}} P_n'$ containing $(\{0\},\emptyset)$ , then $ C_n' \simeq {\mathcal{R}} P_n'/\nu. $ Moreover, for $B,B'\in {\mathcal{R}} P_n'$ we have $B/\nu = B'/\nu$ iff $B\setminus\{0\} =B'\setminus\{0\}$ .

Proof. We first prove the second statement. $\Leftarrow$ : Since $\{0\}/\nu=\emptyset/\nu$ is the least element of ${\mathcal{R}} P_n'/\nu$ , for $B\in {\mathcal{R}} P_n'$ we have

\begin{equation*} B/\nu = \sum\left\{\,\{w\}/\nu\,\mid\,w\in B\,\right\} = \sum\left\{\,\{w\}/\nu\,\mid\,w\in B\setminus\{0\}\,\right\}.\end{equation*}

Hence, if $B,B'\in{\mathcal{R}} P_n'$ with $B\setminus\{0\}=B'\setminus\{0\}$ , then $B/\nu=B'/\nu$ .

$\Rightarrow$ : One shows by induction on the regular operations that

\begin{equation*} \nu_0:=\left\{\,(B,B')\in {\mathcal{R}} P_n'\times {\mathcal{R}} P_n'\,\mid\,B\setminus\{0\} = B'\setminus\{0\}\,\right\}\end{equation*}

is an ${\mathcal{R}}$ -congruence containing $(\{0\},\emptyset)$ , and obviously $\nu\subseteq \nu_0$ .

For the first statement, notice that a congruence class $A/\rho_n$ of $C_n'= {\mathcal{R}}\Delta_n^*/\rho_n$ can be represented by a set of reduced strings, $\left\{\,\textit{nf}_{n}(w)\,\mid\,w\in A\,\right\}\setminus\{0\}$ , and $A/\rho_n\mapsto\left\{\,\textit{nf}_{n}(w)\,\mid\,w\in A\,\right\}/\nu$ constitutes an isomorphism between $C_{n,{\mathcal{R}}}'$ and ${\mathcal{R}} P_n'/\nu$ .

The $n>2$ pairs of brackets $p_i,q_i$ , $i<n$ of $\Delta_n$ can be coded by two pairs, say b,d and p,q of $\Delta_2$ , via $p_i:=bp^i$ and $q_i := q^id$ . This extends to an embedding of $P_n'$ in $P_2'$ .

2.3 The tensor product of ${\mathcal{A}}$ -dioids

In a category whose objects have a monoid structure, two morphisms $F_1:M_1\to M$ and $F_2:M_2\to M$ are relatively commuting, if for all $m_1\in M_1$ and $m_2\in M_2$ , $F_1(m_1)\cdot F_2(m_2) = F_2(m_2) \cdot F_1(m_1)$ .

The tensor product of $M_1$ and $M_2$ is an object $M_1\otimes M_2$ with two relatively commuting morphisms $\top_1 : M_1\to M_1\otimes M_2$ and $\top_2:M_2\to M_1\otimes M_2$ such that for any pair of relatively commuting morphisms $f:M_1\to M$ and $g:M_2\to M$ there is a unique morphism $h_{f,g}: M_1\otimes M_2\to M$ with $f=h_{f,g}\circ \top_1$ and $g=h_{f,g}\circ \top_2$ :

By the universal property, the tensor product of $M_1$ and $M_2$ is unique up to isomorphism.

Example 4. In the category ${\mathbb{M}}$ of monoids, the tensor product of $M_1$ and $M_2$ is the cartesian product $M_1\times M_2$ with componentwise multiplication, unit (1,1) and injections defined by $\top_1(a)=(a,1)$ for $a\in M_1$ and $\top_2(b)=(1,b)$ for $b\in M_2$ . The induced morphism $h_{f,g}$ is the one given by $h_{f,g}(a,b) = f(a)\cdot g(b)$ . $\diamond$

Theorem 10 (Hopkins and Leiß 2018) A tensor product of ${\mathcal{A}}$ -dioids $D_1$ and $D_2$ exists,

\begin{equation*} {\top_1} : {D_1} \longrightarrow {D_1\mathop{\otimes_{\mathcal{A}}} D_2} \longleftarrow {D_2} : {\top_2}, \end{equation*}

consisting of $D_1\mathop{\otimes_{\mathcal{A}}} D_2 := {\mathcal{A}}(M_1\times M_2)/_\equiv$ , where $M_i =\, \widehat{\!{\mathcal{A}}} D_i$ is the monoid underlying $D_i$ and $\equiv$ is the ${\mathcal{A}}$ -congruence generated by the “tensor product relations”

\begin{equation*} \left\{\left(\sum A,\sum B\right)\right\} = A\times B \qquad (A\in{\mathcal{A}}{M_1}, B\in {\mathcal{A}}{M_2}),\end{equation*}

together with the embeddings $\top_1,\top_2$ defined by

\begin{equation*} \top_1(d_1) := \{(d_1,1)\}/_\equiv \,\textrm{ for }d_1\in D_1\textrm{ and }\top_2(d_2) := \{(1,d_2)\}/_\equiv\, \textrm{ for }d_2\in D_2.\end{equation*}

The liftings of the embeddings of $M_i$ into $M_1\times M_2$ map $A\in {\mathcal{A}}M_1$ to $A\times\{1\}\in {\mathcal{A}}(M_1\times M_2)$ and $B\in {\mathcal{A}} M_2$ to $\{1\}\times B \in {\mathcal{A}}(M_1\times M_2);$ hence, $A\times B =(A\times\{1\})(\{1\}\times B)\in {\mathcal{A}}(M_1\times M_2)$ . The tensor product relations are needed to make the $\top_i:D_i \to D_1\mathop{\otimes_{\mathcal{A}}} D_2$ be ${\mathcal{A}}$ -morphisms.

For $U\in{\mathcal{A}}(M_1\times M_2)$ , we write [U] for $U/_\equiv$ . By the definition of $\sum$ on $D_1\mathop{\otimes_{\mathcal{A}}} D_2$ ,

\begin{eqnarray*} [U] &=& \left[\bigcup\left\{\,\{(a,b)\}\,\mid\,(a,b)\in U\,\right\}\right]= \sum \left\{\,[\{(a,b)\}]\,\mid\,(a,b)\in U\,\right\}= \sum \left\{\,a\otimes b\,\mid\,(a,b)\in U\,\right\},\end{eqnarray*}

using $a\otimes b$ for $\top_1(a)\cdot \top_2(b)=[\{(a,b)\}]\in D_1\mathop{\otimes_{\mathcal{A}}} D_2$ . In particular, for $A\in {\mathcal{A}} M_1, B\in {\mathcal{A}} M_2$ , via $A \times B \in {\mathcal{A}}(M_1\times M_2)$ we have, by the tensor product relations,

\begin{equation*} \left(\sum A\right)\otimes \left(\sum B\right) = \sum\left\{\,a\otimes b\,\mid\,a\in A, b\in B\,\right\}.\end{equation*}

Since $D_1\mathop{\otimes_{\mathcal{A}}} D_2 $ is the quotient of ${\mathcal{A}}(M_1\times M_2)$ by the ${\mathcal{A}}$ -congruence $\equiv$ , its partial order is the dioid-order on the quotient, i.e. $[U]\leq [V]$ iff $[U\cup V] = [V]$ for $U,V\in{\mathcal{A}}(M_1\times M_2)$ , which is coarser than the order on ${\mathcal{A}}(M_1\times M_2)$ among the representatives U,V.

Proposition 11 (Hopkins and Leiß 2018) For monoids $M_1$ and $M_2$ , the tensor product of the ${\mathcal{A}}$ -dioids ${\mathcal{A}} M_1$ and ${\mathcal{A}} M_2$ is isomorphic to the ${\mathcal{A}}$ -dioid ${\mathcal{A}}(M_1\times M_2)$ :

\begin{equation*} {\mathcal{A}} M_1\mathop{\otimes_{\mathcal{A}}} {\mathcal{A}} M_2 \ \simeq\ {\mathcal{A}}(M_1\times M_2).\end{equation*}

Proof. (Sketch) The isomorphism ${\mathcal{A}} M_1\mathop{\otimes_{\mathcal{A}}}{\mathcal{A}} M_2\to {\mathcal{A}}(M_1\times M_2)$ maps $[R]=\sum\left\{\,A\otimes B\,\mid\,(A,B)\in R\,\right\}\in {\mathcal{A}} M_1\mathop{\otimes_{\mathcal{A}}} {\mathcal{A}} M_2$ to $\bigcup\left\{\,A\times B\,\mid\,(A,B)\in R\,\right\}$ ⁵ , where $R\in{\mathcal{A}}({\mathcal{A}} M_1 \times {\mathcal{A}} M_2)$ ; the inverse maps $S\in{\mathcal{A}}(M_1\times M_2)$ to $\sum\left\{\,\{a\}\otimes \{b\}\,\mid\,(a,b)\in S\,\right\}$ .

Since $(A,B)\mapsto A\times B$ is a homomorphism from ${\mathcal{A}} M\times {\mathcal{A}}N$ to ${\mathcal{A}}(M\times N)$ , its lifting is a homomorphism from ${\mathcal{A}}({\mathcal{A}}M\times{\mathcal{A}} N)$ to ${\mathcal{A}}({\mathcal{A}}(M\times N))$ , so for $R\in{\mathcal{A}}({\mathcal{A}} M\times {\mathcal{A}} N)$ ,

\begin{equation*} S_R : = \bigcup\left\{\,A\times B\,\mid\,(A,B)\in R\,\right\} \in {\mathcal{A}}(M\times N). \end{equation*}

By the isomorphism, we have $[R]=[R']$ iff $S_R = S_{R'}$ . Conversely, for $S\in{\mathcal{A}}(M\times N)$ ,

\begin{equation*} R_S := \left\{\,(\{a\},\{b\})\,\mid\,(a,b)\in S\,\right\} \in {\mathcal{A}}({\mathcal{A}} M\times {\mathcal{A}} N); \end{equation*}

hence, $[R_S] = \sum\left\{\,\{a\}\otimes\{b\}\,\mid\,(a,b)\in S\,\right\} \in {\mathcal{A}} M\mathop{\otimes_{\mathcal{A}}} {\mathcal{A}}N$ . Notice that $S_{(R_S)}=S$ and $[R_{(S_R)}]=[R]$ .

We can push this a bit further:

Theorem 12. Let M be a monoid and N a monoid with annihilating element 0. Then

(8) \begin{equation}{\mathcal{A}} M\mathop{\otimes_{\mathcal{A}}} ({\mathcal{A}} N/\nu) \simeq {\mathcal{A}}(M\times N)/{\tilde\nu}\end{equation}

where $\nu$ is the least ${\mathcal{A}}$ -congruence on ${\mathcal{A}} N$ containing $(\{0\},\emptyset)$ and ${\tilde\nu}$ is the least ${\mathcal{A}}$ -congruence on ${\mathcal{A}}(M\times N)$ containing $(\{(1,0)\},\emptyset)$ .

Putting $R_\nu := \left\{\,(A,B/\nu)\,\mid\,(A,B)\in R\,\right\}$ for $R\in {\mathcal{A}}({\mathcal{A}}M\times {\mathcal{A}} N)$ , the isomorphism is given by

\begin{eqnarray*} [R_\nu] &\mapsto& (S_R)/{\tilde\nu}, \quad\textrm{where } S_R := \bigcup\left\{\,A\times B\,\mid\,(A,B)\in R\,\right\} \textrm{ for }R\in {\mathcal{A}}({\mathcal{A}} M\times {\mathcal{A}} N),\\ S/{\tilde\nu} &\mapsto& [(R_S)_\nu],\quad\textrm{where }R_S := \left\{\,(\{m\},\{n\})\,\mid\,(m,n)\in S\,\right\} \textrm{ for }S\in {\mathcal{A}}(M\times N).\end{eqnarray*}

Proof. Since $B\mapsto B/\nu$ is a surjective ${\mathcal{A}}$ -morphism from ${\mathcal{A}} N$ to ${\mathcal{A}} N/\nu$ , each element of ${\mathcal{A}}({\mathcal{A}} M\times ({\mathcal{A}} N/\nu))$ is of the form $R_\nu$ for some $R\in {\mathcal{A}}({\mathcal{A}} M\times{\mathcal{A}} N)$ .

To prove ${\mathcal{A}} M\mathop{\otimes_{\mathcal{A}}} ({\mathcal{A}} N/\nu) \simeq {\mathcal{A}}(M\times N)/{\tilde\nu}$ , it is sufficient to show that

\begin{equation*} {\top_1'} : {{\mathcal{A}} M} \longrightarrow {{\mathcal{A}}(M\times N)/{\tilde\nu}} \longleftarrow {{\mathcal{A}} N/\nu} : {\top_2'} \end{equation*}

form a tensor product of ${\mathcal{A}} M$ and ${\mathcal{A}} N/\nu$ in ${\mathbb{D}}{\mathcal{A}}$ , where $\top_1'$ and $\top_2'$ are defined by

\begin{equation*} \top_1'(A) = (A\times\{1\})/{\tilde\nu} \quad\textrm{ and }\quad \top_2'(B/\nu) = (\{1\}\times B)/{\tilde\nu}.\end{equation*}

This will be done in the Appendix.

We here show that the isomorphism ${{\mathcal{A}} M\mathop{\otimes_{\mathcal{A}}} ({\mathcal{A}} N/\nu)}\simeq {{\mathcal{A}}(M\times N)/{\tilde\nu}}$ consisting of the ${\mathcal{A}}$ -morphisms ${h_{\top_1',\top_2'}}$ and ${h'_{\top_1,\top_2}}$ induced by the universal properties of the two tensor product constructions

is as claimed in the theorem. The induced ${\mathcal{A}}$ -morphisms are defined by

\begin{eqnarray*} {h_{\top_1',\top_2'}}([R_\nu]) &:=& \sum\left\{\,\top_1'(A)\cdot\top_2'(B/\nu)\,\mid\,(A,B)\in R\,\right\}\\ &=& \sum\left\{\,(A\times\{1\})/{\tilde\nu}\cdot(\{1\}\times B)/{\tilde\nu}\,\mid\,(A,B)\in R\,\right\}\\ &=& \sum\left\{\,(A\times B)/{\tilde\nu}\,\mid\,(A,B)\in R\,\right\}\\ &=& \left(\bigcup\left\{\,A\times B\,\mid\,(A,B)\in R\,\right\}\right)/{\tilde\nu}= (S_R)/{\tilde\nu}\end{eqnarray*}

and

\begin{eqnarray*} {h'_{\top_1,\top_2}}(S/{\tilde\nu}) &:=& \sum\left\{\,\top_1(\{m\})\cdot\top_2(\{v\}/\nu)\,\mid\,(m,v)\in S\,\right\}\\ &=& \sum\left\{\,\{m\}\otimes \{v\}/\nu\,\mid\,(m,v)\in S\,\right\}\\ &=& [(R_S)_\nu].\end{eqnarray*}

Since $S_{(R_S)} = S$ , we have

\begin{eqnarray*} ({h_{\top_1',\top_2'}}\circ {h'_{\top_1,\top_2}})(S/{\tilde\nu}) &=& {h_{\top_1',\top_2'}}([(R_S)_\nu]) = S_{(R_S)}/{\tilde\nu} = S/{\tilde\nu},\end{eqnarray*}

and since the tensor product embeddings $\top_1,\top_2$ are ${\mathcal{A}}$ -morphisms,

\begin{eqnarray*} ({h'_{\top_1,\top_2}}\circ{h_{\top_1',\top_2'}})([R_\nu]) &=& {h'_{\top_1,\top_2}}(S_R/{\tilde\nu}) = [(R_{(S_R)})_\nu]\\ &=& \sum\left\{\,A\otimes B/\nu\,\mid\,(A,B)\in R_{(S_R)}\,\right\}\\ &=& \sum\left\{\,\{m\}\otimes \{v\}/\nu\,\mid\,(m,v)\in S_R\,\right\}\\ &=& \sum\left\{\,\{m\}\otimes \{v\}/\nu\,\mid\,(m,v)\in A\times B, (A,B)\in R\,\right\}\\ &=& \sum\left\{\,A\otimes B/\nu\,\mid\,(A,B)\in R\,\right\} = [R_\nu]. \\[-28pt]\end{eqnarray*}

With Proposition 9, Theorem 12 provides us with a representation of ${\mathcal{R}} M \mathop{\otimes_{\mathcal{R}}} C_2'$ as a quotient of a free ${\mathcal{R}}$ -dioid extension:

Corollary 13. Let $\nu$ be the least ${\mathcal{R}}$ -congruence on ${\mathcal{R}} P_2'$ containing $(\{0\},\emptyset)$ and ${\tilde\nu}$ the least ${\mathcal{R}}$ -congruence on ${\mathcal{R}}(M\times P_2')$ containing $(\{(1,0)\},\emptyset)$ . Then

\begin{equation*} {\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2' = {\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} ({\mathcal{R}} P_2'/\nu) \simeq {\mathcal{R}}(M\times P_2')/{\tilde\nu}. \end{equation*}

The centralizer $Z_C(D)$ of a set C under an embedding $i:C\to D$ in an ${\mathcal{A}}$ -dioid D is the set

\begin{equation*} \left\{\,d\in D\,\mid\,d\cdot i(c) = i(c)\cdot d \textrm{ for each }c\in C\,\right\}\end{equation*}

of all elements of D that commute elementwise with the image of C in D under i.

In the following, we are concerned with $Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2')$ , the centralizer of $C_2'$ in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ under the tensor product embedding $\top_2 : C_2'\to {\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ .

Proposition 14. For each ${\mathcal{R}}$ -dioid K, $Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is an ${\mathcal{R}}$ -dioid.

Proof. It is clear that $Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is closed under $0,1,+$ and $\cdot$ , so it is a sub-dioid of $K\mathop{\otimes_{\mathcal{R}}} C_2'$ . It is also closed under the restriction of $\sum:{\mathcal{R}}(K\mathop{\otimes_{\mathcal{R}}} C_2')\to K\mathop{\otimes_{\mathcal{R}}} C_2'$ to ${\mathcal{R}}(Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}))$ : if $c\in C_2'$ and $U\in {\mathcal{R}}(Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}))\subseteq {\mathcal{R}}(K\mathop{\otimes_{\mathcal{R}}} C_2')$ , then since $K\mathop{\otimes_{\mathcal{R}}}{C_2'}$ is ${\mathcal{R}}$ -distributive,

\begin{equation*} (1\otimes c)\sum U = \sum\left\{\, (1\otimes c)u\,\mid\,u\in U\,\right\} = \sum\left\{\, u(1\otimes c)\,\mid\,u\in U\,\right\} = \left(\sum U\right)(1\otimes c),\end{equation*}

so $\sum U\in Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ .

We will later see that for monoids M, $Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is a ${\mathcal{C}}$ -dioid and isomorphic to ${\mathcal{C}} M$ . The reason to care about this is that it provides us with regular expressions as a notation system for context-free sets. Every $L\in {\mathcal{C}} M$ is, under ${\mathcal{C}} M \simeq Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ , an element of the Kleene algebra ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ and therefore denoted by a regular expression in the generators of ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ .

Example 5. Let $\Delta_2=\{b,d,p,q\}$ and M be a monoid. For $x,y\in M$ , consider $L = \left\{\,x^ny^n\,\mid\,n\in{\mathbb{N}}\,\right\}\in{\mathcal{C}} M$ and the regular expression $b(px)^*(yq)^*d$ . Interpreted in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ , elements $m\in M$ mean $\top_1(\{m\}) = \{m\}\otimes \{1\}/\nu$ and elements $\delta\in\Delta_2$ mean $\top_2(\{\delta\})=\{1\}\otimes \{\delta\}/\nu$ . By ${}^*$ -continuity and since m and $\delta$ commute with each other in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ , we obtain

\begin{eqnarray*} b(px)^*(yq)^*d &=& b\left(\sum\left\{\,(px)^k\,\mid\,k\in{\mathbb{N}}\,\right\}\right)\left(\sum\left\{\,(yq)^n\,\mid\,n\in{\mathbb{N}}\,\right\}\right)d\\ &=& \sum\left\{\,b(px)^k(yq)^nd\,\mid\,k\in{\mathbb{N}},n\in{\mathbb{N}}\,\right\}\\ &=& \sum\left\{\,x^ky^nbp^kq^nd\,\mid\,k\in{\mathbb{N}},n\in{\mathbb{N}}\,\right\}\\ &=& \sum\left\{\,x^ny^n\,\mid\,n\in{\mathbb{N}}\,\right\},\end{eqnarray*}

where in the final step, $bp^kq^nd = \delta_{k,n}$ since $pq=1=bd$ and $bq=0=pd$ . We will see that for any $L\in {\mathcal{C}} M$ , its image $\widehat L := \sum\left\{\,\{m\}\otimes 1\,\mid\,m\in L\,\right\}$ in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ belongs to $Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ . $\diamond$

To prove that $Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ , together with the embedding $\top_1$ , is the ${\mathcal{C}}$ -closure of ${\mathcal{R}} M$ , we want to show that any ${\mathcal{R}}$ -morphism $f:{\mathcal{R}} M\to C$ to a ${\mathcal{C}}$ -dioid C has a unique extension to a ${\mathcal{C}}$ -morphism $\bar f: Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})\to C$ , which can be defined by

\begin{equation*} \bar f(\widehat L) = \sum\left\{\,f(\{m\})\,\mid\,m\in L\,\right\}\qquad\textrm{ for }L\in{\mathcal{C}} M.\end{equation*}

At least this works if for each element $e\in Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ there is a unique $L\in {\mathcal{C}} M$ with $e=\widehat L$ . This uniqueness condition will be established in the following two sections: by Theorem 17 of Section 3, there is at most one such $L\in {\mathcal{C}} M$ , by Theorem 26 of Section 4, there is at least one such L.

We remark that the category ${\mathbb{D}}{\mathcal{A}}$ has coproducts and free extensions (Hopkins and Leiß 2018). In particular, the free ${\mathcal{A}}$ -dioid extension of ${\mathcal{A}} M$ by the set $\Delta$ , $({\mathcal{A}} M)[\Delta]$ , is isomorphic to ${\mathcal{A}}(M[\Delta])$ , whence we simply write ${\mathcal{A}} M[\Delta]$ below.

3. The CST for Monoids and its Algebraic Version

We now prove the Chomsky–Schützenberger theorem for arbitrary monoids M by reducing ${\mathcal{C}} M$ to ${\mathcal{R}} M$ and the pure Dyck language $D_2\in{\mathcal{C}} \Delta_2^*$ and then give an algebraic version that embeds ${\mathcal{C}} M$ into $Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ . Recall that $\Delta_2$ is an alphabet of two pairs of brackets and $M[\Delta_2]$ the free extension of M by $\Delta_2$ , which is just $(X\cup\Delta_2)^*$ in case $M=X^*$ .

3.1 The CST for monoids

For a finite set X– and $\Delta_2=\{p_0,q_0,p_1,q_1\}$ –, Dyck’s language $D_2(X)\in{\mathcal{C}} X^*[\Delta_2]$ of balanced strings over $X^*[\Delta_2]$ is the least solution of

\begin{equation*} y \geq 1 + X + yy + p_0yq_0 + p_1yq_1 \end{equation*}

in ${\mathcal{P}}(X^*[\Delta_2])$ . By the classical theorem of Chomsky and Schützenberger (1963),

\begin{equation*} {\mathcal{C}} X^* \subseteq\left\{\,h_{X^*}(R\cap D_2(X))\,\mid\,R\in {\mathcal{R}} X^*[\Delta_2]\,\right\}. \end{equation*}

Since, for any monoid M, ${\mathcal{C}} M$ is defined inductively as an extension of ${\mathcal{F}} M$ by least solutions (in ${\mathcal{P}} M$ ) of polynomial systems with parameters from ${\mathcal{C}} M$ , one can reduce the parameters in the polynomial systems to the base case ${\mathcal{F}} M$ , so that all elements of M that occur in the parameters come from a finite set $X\subseteq M$ . Therefore,

\begin{equation*} {\mathcal{C}} M = \bigcup\left\{\,{\mathcal{C}} {\left\langle {X}\right\rangle}\,\mid\,X\in{\mathcal{F}} M\,\right\}, \quad \textrm{likewise }\quad {\mathcal{R}} M = \bigcup\left\{\,{\mathcal{R}} {\left\langle X\right\rangle}\,\mid\,X\in {\mathcal{F}} M\,\right\},\end{equation*}

where ${\left\langle X\right\rangle}\subseteq M$ is the submonoid of M generated by X. We identify a system $y_1\geq p_1,\ldots,y_n\geq p_k$ with polynomials $p_i\in{\mathcal{C}} {\left\langle {X}\right\rangle}[y_1,\ldots,y_k]$ with a context-free grammar with nonterminal symbols $y_1,\ldots,y_k$ , start symbol $y_1$ and terminal symbols from X. Since M resp. $D_2(M)$ belong to ${\mathcal{C}} M$ resp. ${\mathcal{C}} M[\Delta_2]$ only if M is finitely generated, we first state the CST for finitely generated monoids:

Theorem 15 (CST for finitely generated monoids) For any finitely generated monoid M,

\begin{equation*} {\mathcal{C}} M \subseteq \left\{\,h_M(R\cap D_2(M))\,\mid\,R\in {\mathcal{R}} M[\Delta_2]\,\right\}\end{equation*}

where $D_2(M)\in {\mathcal{C}} M[\Delta_2]$ is the set of elements of $M[\Delta_2]$ with balanced brackets.

Our proof is essentially a proof of the classical Chomsky–Schützenberger theorem, with a perhaps more intuitive construction of R from L than can be found in textbooks; it may be helpful to first consider Example 6 below. We use the grammatical definitions of ${\mathcal{C}} M$ and ${\mathcal{R}} M[\Delta_2]$ .

Proof. Let $L_1,\ldots,L_k\in {\mathcal{C}} M$ be the least solution of the grammar $G = {\left\langle {y_1\geq p_1,\ldots,y_k\geq p_k}\right\rangle}$ . We can assume that the parameters in $p_1,\ldots,p_k$ are singletons or empty. Suppose there are $n-1$ occurrences of the variables $y_1,\ldots,y_k$ in $p_1,\ldots,p_k$ . Let $\Delta_n=\{{\langle{0}\!\mid},\ldots,{\langle{n-1}\!\mid},{\langle{0}\!\mid},\ldots,{\mid\!{n-1}\rangle}\}$ be a set of n of “opening brackets” ${\langle{i}\!\mid}$ and n “closing brackets” ${\mid\!{i}\rangle}$ , $i<n$ , and reserve the brackets ${\langle{0}\!\mid},{\langle{0}\!\mid}$ for later usage. Surrounding the i-th variable occurrence by the i-th bracket pair, for $0< i< n$ , turns G into a grammar $G' = \langle y_1\geq p_1',\ldots,y_n\geq p_k'\rangle$ with least solution $L_1',\ldots,L_k'\in {\mathcal{C}} M[\Delta_n]$ . For example, a monomial $m_1y_{j,1}\ldots m_sy_{j,s}m_{s+1}$ of $p_j$ is turned into a monomial $m_1{\langle{i_1}\!\mid}y_{j,1}{\mid\!{i_1}\rangle}\ldots m_s{\langle{i_s}\!\mid}y_{j,s}{\mid\!{i_s}\rangle}m_{s+1}$ of $p_j'$ . By the choice of $p_1',\ldots,p_k'$ , clearly $L_j'\subseteq D_n(M)$ and $L_j = h_M(L_j')$ for $1\leq j\leq k$ .

Approximate $L_1'$ from above by a regular set $R_1\in {\mathcal{R}} M[\Delta_n]$ as follows. To each monomial $\alpha$ of $p_j'$ (i.e. grammar rule $(y_j,\alpha)$ or $y_j\to\alpha$ ) attach a “follow”- or “continuation”-variable $y_j^F$ and split $\alpha y_j^F$ into right-linear factors m’y, where $m'\in M[\Delta_n]$ and $y\in\{y_1,\ldots,y_k,y_j^F\}$ . Let $G^F$ be the right-linear polynomial system

\begin{equation*} y_1 \geq p_1'',\ldots,y_k\geq p_k'',\quad y_1^F \geq p_1^F + 1,\ y_2^F \geq p_2^F,\ldots,y_k^F\geq p_k^F,\end{equation*}

where the monomials of $p_j''$ are the initial factors m’y of the monomials of $p_j'y_j^F$ and those of $p_j^F$ are the factors m’y that follow the occurrences of $y_j$ in $p_1'y_1^F,\ldots,p_k'y_k^F$ . Let $R_1$ be the first component of the least solution of $G^F$ in ${\mathcal{R}} M[\Delta_n]$ .

Claim 1. For all $1\leq j\leq k$ and $w\in M[\Delta_n]$ , if $y_j\Rightarrow_{G'}^* w$ , then $y_j\Rightarrow^*_{G^F} wy_j^F$ .

Proof of Claim 1. By induction on the derivation length $r\geq 1$ in $y_j\Rightarrow^r_{G'} w$ . If $r=1$ , then $y_j\to w$ is a rule of G’, hence $y_j\to wy_j^F$ is a rule of $G^F$ . If $y_j \Rightarrow_{G'}^1 \alpha \Rightarrow_{G'}^r w$ , and the rule $y_j\to\alpha$ of G’ is $y_j\to m_1{\langle{i_1}\!\mid}y_{j,1}{\mid\!{i_1}\rangle}\ldots m_s{\langle{i_s}\!\mid}y_{j,s}{\mid\!{i_s}\rangle}m_{s+1}$ , then $G^F$ has the rules

\begin{equation*} y_j \to m_1{\langle{i_1}\!\mid}y_{j,1},\quad y_{j,1}^F\to {\mid\!{i_1}\rangle}m_2{\langle{i_2}\!\mid}y_{j,2},\quad\ldots,\quad y_{j,s}^F\to {\mid\!{i_s}\rangle}m_{s+1}y_j^F,\end{equation*}

and so $y_j \Rightarrow^*_{G^F} \alpha$ . By the induction hypothesis, we get $\alpha \Rightarrow^*_{G^F} wy_j^F$ ; hence, $y_j \Rightarrow^*_{G^F} wy_j^F$ . $\triangleleft$

Using $y_1^F \geq 1$ , Claim 1 implies $L_1'\subseteq R_1$ ; hence, $L_1'\subseteq R_1\cap D_n(M)$ .

Claim 2. For all $1\leq j\leq k$ and $w\in D_n(M)$ , if $y_j\Rightarrow_{G^F}^* wy_j^F$ , then $y_j\Rightarrow_{G'}^* w$ .

Proof of Claim 2. By induction on the derivation length $r\geq 1$ in $y_j\Rightarrow_{G^F}^rwy_j^F$ . If $r=1$ , then $y_j\to w$ is a rule of G’; hence, $y_j\Rightarrow^*_{G'} w$ . For length $r+1 > 1$ , suppose $y_j\Rightarrow_{G^F}^1 \alpha \Rightarrow_{G^F}^r wy_j^F$ . By the choice of $y_j\geq p_j''$ of $G^F$ , there is $m_1\in M$ such that $\alpha =m_1{\langle{i_1}\!\mid}y_{j,1}$ for some $i_1$ and $y_{j,1}\in \{y_1,\ldots,y_k\}$ , or $\alpha = m_1 y_{j}^F$ . The second case cannot occur, since $m_1y_j^F\Rightarrow_{G^F}^r wy_j^F$ with $r\geq 1$ is impossible: all monomials of $p_j^F$ either begin with a closing bracket ${\mid\!{i}\rangle}$ for some i, or are 1. In the first case, we have $m_1{\langle{i_1}\!\mid}y_{j,1} \Rightarrow_{G^F}^r wy_j^F$ . As $w\in D_n(M)$ , there are $u_1,w_1\in D_n(M)$ such that $w =m_1{\langle{i_1}\!\mid}u_1{\mid\!{i_1}\rangle}w_1$ and $y_{j,1} \Rightarrow_{G^F}^r u_1{\mid\!{i_1}\rangle}w_1y_j^F$ . By the construction of $G^F$ , ${\mid\!{i_1}\rangle}$ occurs only in rules $y_{j,1}^F\to{\mid\!{i_1}\rangle}m_2y_{j}^F$ or $y_{j,1}^F\to {\mid\!{i_1}\rangle}m_2{\langle{i_2}\!\mid}y_{j,2}$ with $m_2\in M$ and $y_{j,2}\in \{y_1,\ldots,y_k\}$ . So we must have

\begin{equation*} y_{j,1} \Rightarrow_{G^F}^{r_1} u_1y_{j,1}^F \Rightarrow_{G^F}^{r_2} u_1 {\mid\!{i_1}\rangle}w_1 y_j^F \quad\textrm{ with }r = r_1+r_2.\end{equation*}

Since $r_1\leq r$ , we get $y_{j,1} \Rightarrow_{G'}^* u_1$ by induction. If the part $y_{j,1}^F \Rightarrow^{r_2}_{G^F} {\mid\!{i_1}\rangle}w_1y_j^F$ is

\begin{equation*} y_{j,1}^F\Rightarrow_{G^F} {\mid\!{i_1}\rangle}m_2 y_{j}^F \Rightarrow^{r_2-1}_{G^F} {\mid\!{i_1}\rangle}w_1y_j^F,\end{equation*}

we must have $r_2=1$ and $w_1=m_2$ , so $y_j \to m_1{\langle{i_1}\!\mid}y_{j,1}{\mid\!{i_1}\rangle}m_2$ is a rule of G’, and since $w=m_1{\langle{i_1}\!\mid}u_1{\mid\!{i_1}\rangle}m_2$ , the claim $y_j\Rightarrow_{G'}^* w$ is shown. If the part $y_{j,1}^F \Rightarrow^{r_2}_{G^F} {\mid\!{i_1}\rangle}w_1y_j^F$ is

\begin{equation*} y_{j,1}^F\Rightarrow_{G^F} {\mid\!{i_1}\rangle}m_2{\langle{i_2}\!\mid}y_{j,2} \Rightarrow^{r_2-1}_{G^F} {\mid\!{i_1}\rangle}w_1y_j^F,\end{equation*}

there are $u_2,w_2\in D_n(M)$ such that $w_1=m_2{\langle{i_2}\!\mid}u_2{\mid\!{i_2}\rangle}w_2$ and $y_{j,2}\Rightarrow_{G^F}^{r_2-1}u_2{\mid\!{i_2}\rangle}w_2$ . As ${\mid\!{i_2}\rangle}$ occurs only in rules $y_{j,2}^F\to{\mid\!{i_2}\rangle}m_3y_j^F$ or $y_{j,2}^F\to{\mid\!{i_2}\rangle}m_3{\langle{i_3}\!\mid}y_{j,3}$ with $m_3\in M$ and $y_{j,3}\in\{y_1,\ldots,y_k\}$ , we can continue this way and get $1\leq i_1,\ldots,i_s\leq n$ , $r_1,\ldots,r_s\leq r$ , $m_1,\ldots,m_{s+1}\in M$ and $u_1,\ldots,u_s\in D_n(M)$ such that $w=m_1{\langle{i_1}\!\mid}u_1{\mid\!{i_1}\rangle}\ldots m_s{\langle{i_s}\!\mid}u_{s}{\mid\!{i_s}\rangle}m_{s+1}$ and

\begin{eqnarray*}y_j\Rightarrow_{G^F} m_1{\langle{i_1}\!\mid}y_{j,1}, && \quad y_{j,1}\Rightarrow_{G^F}^{r_1} u_1 y_{j,1}^F,\quad y_{j,1}^F \Rightarrow_{G^F} {\mid\!{i_1}\rangle}m_2{\langle{i_2}\!\mid} y_{j,2}, \quad\ldots\\ & &{j,s}\Rightarrow_{G^F}^{r_s} u_s y_{j,s}^F,\quad y_{j,s}^F\Rightarrow_{G^F} {\mid\!{i_s}\rangle}m_{s+1} y_{j}^F.\end{eqnarray*}

By construction of $G^F,$ there is a rule $y_j\to m_1{\langle{i_1}\!\mid}y_{j,1}{\mid\!{i_1}\rangle}\ldots{\langle{i_s}\!\mid}y_{j,s}{\mid\!{i_s}\rangle}m_{s+1}$ in G’, and by induction, $y_{j,1}\Rightarrow_{G'}^* u_1,\ \ldots,\ y_{j,s}\Rightarrow^*_{G'} u_s$ . The claim $y_j\Rightarrow^*_{G'} w$ follows. $\triangleleft$

Using $y_1^F\Rightarrow_{G^F} 1$ , Claim 2 implies $R_1\cap D_n(M)\subseteq L_1'$ . So $L_1'=R_1\cap D_n(M)$ , and $L_1= h_M(L_1')=h_M(R_1\cap D_n(M))$ . Finally, $D_n(M)$ can be replaced by $D_2(M)$ , since two bracket pairs b,d and p,q can be used to code ${\langle{i}\!\mid}$ by $bp^i$ and ${\mid\!{i}\rangle}$ by $q^id$ for $i< n$ .

Example 6. Let $a,b,c\in M$ and let $G = {\left\langle {y\geq p_y(y,z), z\geq p_z(y,z)}\right\rangle}$ be the following grammar

\begin{equation*} \begin{array}{rcl@{\qquad}rcl} y &\geq& a + bzc, & z &\geq& yy,\end{array}\end{equation*}

which defines sets $L_y,L_z\in{\mathcal{C}} M$ . Adding brackets around the three variable occurrences on the right turns G into the grammar $G' = {\left\langle {y\geq p_y', z\geq p_z'}\right\rangle}$

\begin{equation*} \begin{array}{rcl@{\qquad}rcl} y &\geq& a + b{\langle{l}\!\mid}z{\mid\!{1}\rangle}c, & z &\geq& {\langle{2}\!\mid}y{\mid\!{2}\rangle}{\langle{3}\!\mid}y{\mid\!{3}\rangle},\end{array}\end{equation*}

defining $L_y',L_z'\in{\mathcal{C}} M[\Delta_3]$ . It is clear that $L_y = h_M(L_y')$ and $L_y'\subseteq D_4(M)$ . Now add follow- or continuation-variables to the summands of $p_y'$ resp. $p_z'$

\begin{equation*} \begin{array}{rcl@{\qquad}rcl} y &\geq& ay^F + b{\langle{l}\!\mid}z{\mid\!{1}\rangle}cy^F, & z &\geq& {\langle{2}\!\mid}y{\mid\!{2}\rangle}{\langle{3}\!\mid}y{\mid\!{3}\rangle}z^F;\end{array}\end{equation*}

now split the monomials of $p_y'y^F$ and $p_z'z^F$ into right-linear factors mx with $m\in M[\Delta_3]$ and $x\in \{y,z,y^F,z^F\}$ to build the right-linear grammar $G^F = {\left\langle {y\geq p_y'', z\geq p_z'', y^F\geq p_y^F + 1,z^F\geq p_z^F}\right\rangle}$ where $p_y''$ resp. $p_z''$ are the sums of the initial factors from $p_y'y^F$ resp. $p_z'z^F$ , and $p_y^F$ resp. $p_z^F$ are the sums of factors following an occurrence of y resp. z in $p_y'y^F$ and $p_z'z^F$ :

(9) \begin{equation} \begin{array}{rcl@{\qquad}rcl@{\qquad}rcl@{\qquad}rcl} y &\geq& a y^F + b{\langle{l}\!\mid}z, & z &\geq& {\langle{2}\!\mid}y,& y^F &\geq& {\mid\!{2}\rangle}{\langle{3}\!\mid}y + {\mid\!{3}\rangle}z^F + 1, & z^F &\geq& {\mid\!{1}\rangle}c y^F.\end{array}\end{equation}

We need $y^F\geq 1$ , since y is the start symbol of G. Let $R_y\in {\mathcal{R}}M[\Delta_3]$ be the y-component of the least solution of $G^F$ . Intuitively, $L_y'\subseteq R_y$ since $y^F$ collects what follows any occurrence of y. A finite automaton accepting $R_y$ is shown in Figure 1 (with initial node y and accepting node $y^F$ ). A regular expression for $R_y$ can be obtained by solving the inequation system in Kleene algebra (i.e. replace $x \geq Ax+B$ with constant A,B by $x=A^*B$ ) with respect to y. This leads via $z^F={\mid\!{1}\rangle} cy^F$ ,

\begin{eqnarray*} y^F &=& {\mid\!{2}\rangle}{\langle{3}\!\mid}y + {\mid\!{3}\rangle}{\mid\!{1}\rangle}c y^F +1\\ &=& ({\mid\!{3}\rangle}{\mid\!{1}\rangle}c)^*({\mid\!{2}\rangle}{\langle{3}\!\mid}y+1)\\ &=& ({\mid\!{3}\rangle}{\mid\!{1}\rangle}c)^*{\mid\!{2}\rangle}{\langle{3}\!\mid}y + ({\mid\!{3}\rangle}{\mid\!{1}\rangle}c)^*\end{eqnarray*}

and $z = {\langle{2}\!\mid} y$ to the least solution in y by

\begin{eqnarray*} y &=& a y^F + b{\langle{l}\!\mid}{\langle{2}\!\mid}y\\ &=& a ({\mid\!{3}\rangle}{\mid\!{1}\rangle}c)^*{\mid\!{2}\rangle}{\langle{3}\!\mid}y + a ({\mid\!{3}\rangle}{\mid\!{1}\rangle}c)^* + b{\langle{l}\!\mid}{\langle{2}\!\mid}y\\ &=& (b{\langle{l}\!\mid}{\langle{2}\!\mid} + a ({\mid\!{3}\rangle}{\mid\!{1}\rangle}c)^*{\mid\!{2}\rangle}{\langle{3}\!\mid})y + a({\mid\!{3}\rangle}{\mid\!{1}\rangle}c)^*\\ &=& (b{\langle{l}\!\mid}{\langle{2}\!\mid}+ a ({\mid\!{3}\rangle}{\mid\!{1}\rangle}c)^*{\mid\!{2}\rangle}{\langle{3}\!\mid})^* a({\mid\!{3}\rangle}{\mid\!{1}\rangle}c)^*.\end{eqnarray*}

For example, $R_y$ contains the description $b{\langle{l}\!\mid}{\langle{2}\!\mid}a{\mid\!{2}\rangle}{\langle{3}\!\mid}a{\mid\!{3}\rangle}{\mid\!{1}\rangle}c$ of a parse tree of $baac\in L_y$ .

Let us add a preview to the algebraic version of the theorem and its reverse. Those elements of $R_y$ that are not descriptions of parse trees of words in $L_y$ contain (modulo commuting brackets with elements of M) bracket mismatches or have initial closing brackets or final opening brackets, like $w=a{\mid\!{3}\rangle} {\mid\!{1}\rangle} c{\mid\!{2}\rangle}{\langle{3}\!\mid}a\in R_y$ . With the reserved pair ${\langle{0}\!\mid},{\langle{0}\!\mid}$ of brackets, we can go from $R_y$ to $\{{\langle{0}\!\mid}\}R_y\{{\langle{0}\!\mid}\}$ and thereby turn the latter kind of elements into further ones with bracket mismatches, like ${\langle{0}\!\mid} w{\langle{0}\!\mid} = {\langle{0}\!\mid} a{\mid\!{3}\rangle}{\mid\!{1}\rangle} c{\mid\!{2}\rangle}{\langle{3}\!\mid} a{\langle{0}\!\mid}$ . The modified automaton shown in Figure 2 therefore is a description of $L_y$ : if we only extract sequences without bracket mismatches, we obtain all parse trees of words in $L_y$ . An algorithm to extract only bracket mismatch-free strings from a similar automaton is given by Hulden (2011) for a CFG-parser based on the Chomsky–Schützenberger theorem.

Figure 2. automaton for $R_y\in{\mathcal{R}} M[\Delta_3]$ .

Figure 3. automaton for $L_y\in {\mathcal{C}} M \simeq Z_{C_4'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_4'})$ .

A version without the assumption that M be finitely generated follows:

Corollary 16 (CST for monoids). Let M be a monoid M and $D_2 \in {\mathcal{C}}\Delta_2^*$ the pure Dyck language over $\Delta_2$ . For any $L\in {\mathcal{C}} M,$ there is some $R\in {\mathcal{R}}(M\times\Delta_2^*)$ such that

\begin{equation*} L = \left\{\,m\,\mid\,(m,d)\in R, d\in D_2\,\right\}. \end{equation*}

Moreover, for $(m,d)\in R$ the normal form $\textit{nf}_{2}(d)$ in $P_2'=Q_2^*P_2^*\cup\{0\}$ of d belongs to $\{0,1\}$ .

Proof. For each $L\in {\mathcal{C}} M,$ there is a finitely generated submonoid $N\subseteq M$ with $L\in{\mathcal{C}} N$ , and by Theorem 15, there is $S\in{\mathcal{R}} N[\Delta_2]$ such that $L= h_N(S\cap D_2(N))$ . The homomorphism ${\left\langle {h_N,h_{\Delta_2^*}}\right\rangle} : N[\Delta_2]\to N\times \Delta_2^*$ lifts to a homomorphism $h:{\mathcal{R}} N[\Delta_2]\to {\mathcal{R}}(N\times\Delta_2^*)\subseteq {\mathcal{R}}(M\times \Delta_2^*)$ . Then, $R := h(S) \in{\mathcal{R}}(M\times \Delta_2^*)$ and $L = h_N(S\cap D_2(N)) = \pi_1(R\cap (M\times D_2))$ , where $\pi_1:M\times \Delta_2^*\to M$ is the first projection.

The normal form $\textit{nf}_{2}:(\Delta_2\cup\{0\})^*\to P_2'=Q_2^*P_2^*\cup\{0\}$ maps those $d\in\Delta_2^*$ with $d\in D_2$ to $1\in Q_2^*P_2^*$ and those containing a bracket mismatch to 0. To obtain $\textit{nf}_{2}(d)\in \{0,1\}$ for all $(m,d)\in R$ , the idea is to wrap all strings of $\Delta_2^*$ with a third pair of brackets; this turns strings with normal form 0 or 1 into strings with the same normal form and those with normal form in $Q_2^*P_2^*\setminus\{1\}$ into strings with normal form 0, because of a mismatch with the new wrapping brackets; finally, the three bracket pairs are coded by two.

To carry this out, suppose $\Delta_2=\{{\langle{0}\!\mid},{\langle{0}\!\mid},{\langle{1}\!\mid},{\mid\!{1}\rangle}\}$ . The embedding of $\Delta_2$ in $\Delta_2^*$ given by ${\langle{i}\!\mid} \mapsto{\langle{0}\!\mid}{\langle{1}\!\mid}^{i+1}$ and ${\mid\!{i}\rangle} \mapsto {\mid\!{1}\rangle}^{i+1}{\langle{0}\!\mid}$ for $i<2$ extends to a homomorphism $':\Delta_2^*\to\Delta_2^*$ , such that $d \in D_2$ iff $d'\in D_2$ for each $d\in \Delta_2^*$ . Then, $(m,d) \mapsto(m,d')$ also is a homomorphism, which lifts to a homomorphism from ${\mathcal{R}}(M\times \Delta_2^*)$ to ${\mathcal{R}}(M\times\Delta_2^*)$ . From $R\in{\mathcal{R}}(M\times \Delta_2^*),$ we therefore obtain $R':= \left\{\,(m,d')\,\mid\,(m,d)\in R\,\right\}\in{\mathcal{R}}(M\times\Delta_2^*)$ ; hence, also

\begin{equation*} \widetilde R := \{(1,{\langle{0}\!\mid})\}\cdot R'\cdot \{(1,{\mid\!{0}\rangle})\}\in {\mathcal{R}}(M\times\Delta_2^*). \end{equation*}

For $d\in\Delta_2^*,$ we have $d\in D_2$ iff $d'\in D_2$ iff ${\langle{0}\!\mid} d'{\langle{0}\!\mid}\in D_2$ , so $\textit{nf}_{2}(d)=1$ iff $\textit{nf}_{2}{{\langle{0}\!\mid}d'{\langle{0}\!\mid}}=1$ , and

\begin{equation*} L=\left\{\,m\,\mid\,(m,d)\in R, d\in D_2\,\right\} = \left\{\,m\,\mid\,(m,\tilde d)\in \widetilde R, \tilde d\in D_2\,\right\}. \end{equation*}

Moreover, if $\textit{nf}_{2}(d)=0$ , then $\textit{nf}_{2}{{\langle{0}\!\mid} d'{\langle{0}\!\mid}}=0$ . Finally, if $\textit{nf}_{2}(d)\in Q_2^*P_2^*\setminus\{1\}$ , then $\textit{nf}_{2}{d'}$ begins with ${\mid\!{1}\rangle}^{i+1}{\langle{0}\!\mid}$ or ends in ${\langle{0}\!\mid}{\langle{1}\!\mid}^{i+1}$ , for some $i<2$ , so that $\textit{nf}_{2}{{\langle{0}\!\mid}d'{\mid\!{0}\rangle}}=0$ . Hence, with $\widetilde R$ instead of R both claims in the statement of the corollary hold.

3.2 Algebraic version of the CST for monoids

In the algebraic formulation, the Chomsky–Schützenberger theorem relates the objects ${\mathcal{R}} M$ and ${\mathcal{C}} M$ of the Kleisli subcategories of ${\mathbb{D}}{\mathcal{R}}$ and ${\mathbb{D}}{\mathcal{C}}$ . While in the classical formulation, each $L\in{\mathcal{C}} M$ has a regular approximation $R\in{\mathcal{R}} M[\Delta_2]$ such that $L=h_M(R\cap D_2(M))$ , one can now perform both the intersection with $D_2(M)$ and the removal of brackets by $h_M$ algebraically in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ , and the relation between L and R becomes one of representing the same tensor.

Theorem 17 (Algebraic CST for monoids) For any monoid M and $L\in{\mathcal{C}} M$ , the elementwise $\top_1$ -image $\left\{\,\{m\}\otimes 1\,\mid\,m\in L\,\right\}\in {\mathcal{C}}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2')$ of L has a least upper bound in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ ,

\begin{equation*} \sum\left\{\,\{m\}\otimes 1\,\mid\,m\in L\,\right\}. \end{equation*}

In fact, there is an injective map $\widehat{\,\cdot\,}: {\mathcal{C}} M \to Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2')$ given by

\begin{equation*} L\ \mapsto\ \widehat L := \sum\left\{\,\{m\}\otimes 1\,\mid\,m\in L\,\right\}. \end{equation*}

Proof. By Corollary 16, for $L\in{\mathcal{C}} M$ there is $S\in{\mathcal{R}}(M\times \Delta_2^*)$ with $L = \left\{\,m\,\mid\,(m,d)\in S, d\in D_2\,\right\}$ , and the normal form $\textit{nf}_{2}(d)$ of each $d\in\Delta_2^*$ with $(m,d)\in S$ belongs to $\{0,1\}\subset P_2'$ . There is an isomorphism ${\mathcal{R}}(M\times\Delta_2^*) \simeq {\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}}{\mathcal{R}}\Delta_2^*$ which maps $S\in{\mathcal{R}}(M\times\Delta_2^*)$ to the congruence class of

\begin{equation*} R_S = \left\{\,(\{m\},\{d\})\,\mid\,(m,d)\in S\,\right\} \in {\mathcal{R}}({\mathcal{R}} M\times {\mathcal{R}}{\Delta_2^*}).\end{equation*}

By definition, using $\{m\}\otimes \{d\} := [\{(\{m\},\{d\})\}]$ , this congruence class is

\begin{eqnarray*} [R_S] &=& \sum\left\{\,\{m\}\otimes \{d\}\,\mid\,(m,d)\in S\,\right\}\in {\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}}{\mathcal{R}}\Delta_2^*,\end{eqnarray*}

where $\sum$ is the least upper bound in the tensor product. The canonical map $\cdot/\rho_2:{\mathcal{R}}\Delta_2^*\to C_2' = {\mathcal{R}}\Delta_2^*/\rho_2$ is an ${\mathcal{R}}$ -morphism mapping those $\{d\}$ with $d\in D_2$ to $1\in C_2'$ and those where d contains a bracket mismatch to $0\in C_2'$ . By the assumption on S, for all $(m,d)\in S$ either $\textit{nf}_{2}(d)=1$ , i.e. $d\in D_2$ , or $\textit{nf}_{2}(d)=0$ , i.e. d contains a bracket mismatch. Hence for all d with $(m,d)\in S$ ,

\begin{equation*} d\in D_2 \iff \{d\}/\rho_2 = 1, \qquad d\notin D_2 \iff \{d\}/\rho_2 = 0. \end{equation*}

The image of $R_S$ under the homomorphism $h := {Id}\times \cdot/\rho_2:{\mathcal{R}} M\times{\mathcal{R}}\Delta_2^*\to{\mathcal{R}} M\times C_2'$ is

\begin{equation*} \left\{\,(\{m\},\{d\}/\rho_2)\,\mid\,(m,d)\in S\,\right\} \in {\mathcal{R}}({\mathcal{R}} M\times C_2'), \end{equation*}

and therefore, since $\{m\}\otimes 0 = 0$ ,

\begin{eqnarray*} \sum\left\{\,\{m\}\otimes 1\,\mid\,m\in L\,\right\} &=& \sum\left\{\,\{m\}\otimes \{d\}/\rho_2\,\mid\,(m,d)\in S, d\in D_2\,\right\}\\ &=& \sum\left\{\,\{m\}\otimes \{d\}/\rho_2\,\mid\,(m,d)\in S\,\right\}\\ &=& \left[\left\{\,(\{m\},\{d\}/\rho_2)\,\mid\,(m,d)\in S\,\right\}\right] \in {\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'.\end{eqnarray*}

Since each $\{m\}\otimes 1$ and $\{m\}\otimes 0$ commutes with each $1\otimes c$ for $c\in C_2'$ , we have

\begin{equation*} \widehat L = \sum\left\{\,\{m\}\otimes 1\,\mid\,m\in L\,\right\}\in Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2') \end{equation*}

by the ${\mathcal{R}}$ -distributivity of ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ .

To show that the map $L\mapsto \widehat L$ is injective, we present two relatively commuting ${\mathcal{R}}$ -morphisms f,g such that the induced ${\mathcal{R}}$ -morphism $h_{f,g}$ maps $\widehat L$ back to a copy of L.

Let f be defined by $f(A) = A \otimes I$ for $A\in{\mathcal{R}} M$ , where $I\in{\textit Mat}_{{P_2^*},{P_2^*}}({\mathbb{B}})$ is the unit matrix. By g we interpret $C_2'$ in ${\textit Mat}_{{P_2^*},{P_2^*}}({\mathbb{B}})$ , which is isomorphic to the ${\mathcal{P}}$ -dioid of binary relations over $P^*_2$ , the “stack part” of $P_2' =(Q_2^*P_2^*\cup\{0\},\cdot,1)$ . To define g, let $\gamma: \Delta_2^*\to{\textit Mat}_{{P_2^*},{P_2^*}}({\mathbb{B}})$ be the homomorphism generated by the relations “push $p_i$ ” and “pop $p_i$ ” on the stack part $P_2^*$ of $P_2'$ ,

\begin{eqnarray*} \gamma(p_i) &:=& \left\{\,(u,v)\in P_2^*\times P_2^*\,\mid\,u\cdot p_i = v\,\right\}, \\ \gamma(q_i) &:=& \left\{\,(u,v)\in P_2^*\times P_2^*\,\mid\,u\cdot q_i = v\,\right\} \end{eqnarray*}

for $i<2$ . Clearly, $\gamma$ extends to an ${\mathcal{R}}$ -morphism $\gamma^*:{\mathcal{R}}\Delta_2^*\to {\textit Mat}_{{P_2^*},{P_2^*}}({\mathbb{B}})$ by

\begin{equation*} \gamma^*(U) = \sum\left\{\,\gamma(u)\,\mid\,u\in U\,\right\}. \end{equation*}

The semiring equations $p_iq_j=\delta_{i,j}$ hold in ${\textit Mat}_{{P_2^*},{P_2^*}}({\mathbb{B}})$ when 0 and 1 are interpreted by the matrices 0 and I, and $p_i$ and $q_j$ by $\gamma^*(\{p_i\})$ and $\gamma^*(\{q_j\})$ , for $i<2$ . Therefore, $\gamma^*$ is constant on $\rho_2$ -congruence classes, and hence,

\begin{equation*} g(U/\rho_2) = \{1\}\otimes \gamma^*(U), \quad\textrm{ for }U\in{\mathcal{R}}\Delta_2^*,\end{equation*}

defines an ${\mathcal{R}}$ -morphism $g:C_2'\to{\mathcal{P}} M\mathop{\otimes_{\mathcal{P}}} {\textit Mat}_{{P_2^*},{P_2^*}}({\mathbb{B}})$ . Obviously, f and g are relatively commuting.

By the choice of S for $L\in{\mathcal{C}} M,$ we have $L=\left\{\,m\,\mid\,(m,d)\in S, d\in D_2\,\right\}$ and

\begin{equation*} \{d\}/\rho_2 = \begin{cases} 1 & d \in \pi_2(S) \cap D_2, \\ 0 & d \in \pi_2(S) \setminus D_2.\end{cases}\end{equation*}

So $g(\{d\}/\rho_2)$ is the unit matrix for $d\in \pi_2(S)\cap D_2$ and the zero matrix for $d\in\pi_2(S)\setminus D_2$ . As $h_{f,g}$ is an ${\mathcal{R}}$ -morphism and $\left\{\,\{m\}\otimes \{d\}/\rho_2\,\mid\,(m,d)\in S\,\right\}\in{\mathcal{R}}({\mathcal{R}} M \mathop{\otimes_{\mathcal{R}}} C_2')$ , we obtain

\begin{eqnarray*} h_{f,g}(\widehat L) &=& h_{f,g}\left(\sum\left\{\,\{m\}\otimes 1\,\mid\,m\in L\,\right\}\right)\\ &=& h_{f,g}\left(\sum\left\{\,\{m\}\otimes \{d\}/\rho_2\,\mid\,(m,d)\in S\,\right\}\right)\\ &=& \sum\left\{\,h_{f,g}(\{m\}\otimes \{d\}/\rho_2)\,\mid\,(m,d)\in S\,\right\}\\ &=& \sum\left\{\,f(\{m\})\cdot g(\{d\}/\rho_2)\,\mid\,(m,d)\in S\,\right\}\\ &=& \sum\left\{\,\{m\}\otimes I\,\mid\,m\in L\,\right\}\\ &=& L\otimes I,\end{eqnarray*}

using the ${\mathcal{C}}$ -continuity of the embedding $\top_1':{\mathcal{P}} M \to {\mathcal{P}} M\mathop{\otimes_{\mathcal{P}}}{\textit Mat}_{{P_2'},{P_2'}}({\mathbb{B}})$ in the final step. Since $\top_1'$ is injective, $h_{f,g}$ is essentially an inverse to $L \mapsto \widehat L$ . ⁶

4. The Reverse CST for Monoids and its Algebraic Version

The “reverse” Chomsky–Schützenberger theorem, i.e. that for finite X,

\begin{equation*} \left\{\,h_{X^*}(R\cap D_2(X))\,\mid\,R\in {\mathcal{R}}(X^*[\Delta_2])\,\right\}\subseteq {\mathcal{C}} X^*, \end{equation*}

involves showing that $R\cap D_2(X)\in {\mathcal{C}}(X^*[\Delta_2])$ , which is usually done by coupling a finite-state acceptor with a pushdown automaton. This construction does not work for an arbitrary finitely generated monoid M, since there is no standard presentation of elements of M as a sequence of elements from a finite generating subset; we therefore give a grammatical proof of $h_M(R\cap D_2(M))\in{\mathcal{C}} M$ below. A version of a reverse CST for arbitrary monoids follows.

4.1 The reverse CST for monoids

If M is a finitely generated monoid, M belongs to ${\mathcal{C}} M$ and $D_2(M)$ to ${\mathcal{C}}(M[\Delta_2])$ . So we can formulate the reverse CST for such M as direct generalization from the classical case.

Theorem 18 (Reverse CST for finitely generated monoids). For any finitely generated monoid M,

\begin{equation*} \left\{\,h_M(R\cap D_2(M))\,\mid\,R\in {\mathcal{R}} (M[\Delta_2])\,\right\} \subseteq {\mathcal{C}} M. \end{equation*}

Proof. Since the erasing homomorphism $h_M:M[\Delta_2]\to M$ lifts to $h_M:{\mathcal{C}}(M[\Delta_2])\to {\mathcal{C}} M$ , it is sufficient to show

(10) \begin{equation} \left\{\,R\cap D_2(M)\,\mid\,R\in {\mathcal{R}} (M[\Delta_2])\,\right\} \subseteq {\mathcal{C}} (M[\Delta_2]).\end{equation}

Suppose $R\in {\mathcal{R}}(M[\Delta_2])$ . Then, R is a component of the least solution $\vec R$ of a system

\begin{equation*} y_1 \geq p_1(y_1,\ldots,y_n),\ \ldots,\ y_n\geq p_n(y_1,\ldots,y_n) \end{equation*}

with right-linear polynomials $p_1,\ldots,p_n\in {\mathcal{F}}(M[\Delta_2])[y_1,\ldots,y_n]$ . By means of additional variables and inequations, we can assume that all parameters from ${\mathcal{F}}(M[\Delta_2])$ are singletons or the empty set, so that the system can be written as

(11) \begin{eqnarray} y_1 &\geq& w_{1,1}y_1 + \ldots + w_{1,n}y_n + w_1, \nonumber\\ &\vdots& \end{eqnarray}

\begin{eqnarray} y_n &\geq& w_{n,1}y_1 + \ldots + w_{n,n}y_n + w_n, \nonumber\end{eqnarray}

where the parameters $w_{i,j},w_i$ are from $M[\Delta_2]$ , standing for the singletons $\{w_{i,j}\}$ resp. $\{w_i\}$ , or are 0 and stand for $\emptyset$ . As any $w\in M[\Delta_2]$ is an interleaving sequence of products of generators of M and elements of $\Delta_2$ , we can further assume that $w_{i,j}\in X\cup\Delta_2\cup\{0\}$ and $w_i \in \{0,1\}$ , where X is the finite set of generators of M. Then, $\vec R$ can be obtained by first taking the least solution of (11) in ${\mathcal{R}}(X^*[\Delta_2])$ and then interpreting sequences $m_1\cdots m_k\in X^*$ by the product $m_1\cdot^M \cdots \cdot^M m_k\in M$ of their members. Let $D_2(M)\in{\mathcal{C}}(M[\Delta_2])$ be the likewise interpretation of the Dyck language $D_2(X)\in{\mathcal{C}}(X^*[\Delta_2])$ . To show $R\cap D_2(M)\in {\mathcal{C}}(M[\Delta_2])$ , we construct a context-free grammar G, the least solution of which assigns $R\cap D_2(M)$ to its main variable S. The variables Y of G are S and all [y,D,z], [y,d,z] and [y,D,1] with $y,z\in\{y_1,\ldots,y_n\}, d\in\Delta_2$ and auxiliary symbol D. Its inequations $Y \geq \alpha_1+\ldots+\alpha_k$ are obtained by combining all inequations $Y\geq \alpha_1,\ldots, Y\geq \alpha_k$ with the same left hand side Y from the following table:

Claim 1. For all $y\in\{y_1,\ldots,y_n\}$ and $z\in \{y_1,\ldots,y_n\}\cup\{1\}$ , $[y,D,z] \Rightarrow^*_G w$ and $w\in M[\Delta_2]$ iff $y\Rightarrow^*_R wz$ and $w\in D_2(X)$ .

Proof of Claim 1. $\Rightarrow$ : This is easily shown by induction on k in $[y,D,z] \Rightarrow^k_G w$ .

$\Leftarrow$ : Suppose $y\Rightarrow^k_R wz$ and $w\in D_2(X)$ . There is a sequence

\begin{equation*} y_{i_0} \geq w_1 y_{i_1},\quad y_{i_1} \geq w_2 y_{i_2},\quad \ldots, \quad y_{i_{k-1}}\geq w_ky_{i_k} \end{equation*}

such that $y=y_{i_0}$ , $w=w_1\cdots w_k\in D_2(X)$ and $y_{i_k}=z$ . We show by induction on k that

\begin{equation*} [y_{i_0},D,y_{i_k}]\Rightarrow^*_G w_{1}\cdots w_k. \end{equation*}

If $k=0$ , then $w = 1$ , and $[y_{i_0},D,y_{i_0}]\Rightarrow_G 1$ . If $k=1$ , then $y_{i_0}\geq wy_{i_1}$ and $w\in X\cup\Delta_2$ . From $w\in D_2(X),$ we get $w\in X$ , hence $[y_{i_0},D,y_{i_1}]\Rightarrow_G w$ .

Suppose $k>1$ . By the construction of $D_2(X)$ , there either is $j<k$ with $u:=w_1\cdots w_j, v:=w_{j+1}\cdots w_k\in D_2(X)$ and $w=uv$ , or $w =p_0uq_0$ or $w=p_1uq_1$ with $u:=w_2\cdots w_{k-1}\in D_2(X)$ .

In the first case, we have $y_{i_0} \Rightarrow^*_R uy_{i_j}$ and $y_{i_j}\Rightarrow^*_R vy_{i_k}$ in less than k steps; hence, $[y_{i_0},D,y_{i_j}]\Rightarrow^*_Gu$ and $[y_{i_j},D,y_{i_k}]\Rightarrow^*_G v$ by induction; hence,

\begin{equation*} [y_{i_0},D,y_{i_k}]\Rightarrow_G [y_{i_0},D,y_{i_j}][y_{i_j},D,y_{i_k}] \Rightarrow^*_G uv = w.\end{equation*}

In the second case, we have $y_{i_1}\Rightarrow^*_R uy_{i_{k-1}}$ in less than k steps; hence, $[y_{i_1},D,y_{i_{k-1}}]\Rightarrow^*_G u$ by induction; hence for $j\in\{0,1\}$ ,

\begin{eqnarray*} [y_{i_0},D,y_{i_k}]&\Rightarrow_G& [y_{i_0},p_j,y_{i_1}][y_{i_1},D,y_{i_{k-1}}][y_{i_{k-1}},q_j,y_{i_k}]\\ &\Rightarrow_G^2& p_j[y_{i_1},D,y_{i_{k-1}}]q_j\Rightarrow^*_G p_juq_j = w.\triangleleft\end{eqnarray*}

It follows that G defines $R\cap D_2(X)$ : If $w\in L(G)$ , then $S \Rightarrow^*_G w\in M[\Delta_2]$ , so by the claim, $w\in R\cap D_2(X)$ . Conversely, if $y\Rightarrow^*_Rwz$ and y is the main variable of (11), then $S\Rightarrow_G [y,D,z] \Rightarrow^*_G w$ , so $w\in L(G)$ .

As with the CST, a version of the reverse CST for arbitrary monoids follows:

Corollary 19 (Reverse CST for monoids). For any monoid M and $R\in {\mathcal{R}}(M\times \Delta_2^*)$ ,

\begin{equation*} \left\{\,m\,\mid\,(m,d)\in R, d\in D_2\,\right\} \in {\mathcal{C}} M. \end{equation*}

Proof. If $R\in {\mathcal{R}}(M\times \Delta_2^*)$ , there is a finitely generated submonoid $N\subseteq M$ with $R\in{\mathcal{R}}(N\times \Delta_2^*)$ . The homomorphism ${\left\langle {h_N,h_{\Delta_2^*}}\right\rangle} : N[\Delta_2]\to N\times \Delta_2^*$ is surjective and lifts to a surjective homomorphism $h:{\mathcal{R}} N[\Delta_2]\to{\mathcal{R}}(N\times \Delta_2^*)$ , by Theorem 1. So there is $S\in{\mathcal{R}} N[\Delta_2]$ with $R= h(S)$ . For any $(m,d)\in R$ there is $w\in S$ with $(m,d)={\left\langle {h_N,h_{\Delta_2^*}}\right\rangle}(w) = (h_N(w),h_{\Delta_2^*}(w))$ . Then, $d\in D_2$ iff $w\in D_2(N)$ iff $w\in S\cap D_2(N)$ iff $m\in h_N(S\cap D_2(N))$ . Hence,

\begin{equation*} \left\{\,m\,\mid\,(m,d)\in R, d\in D_2\,\right\} = h_N(S\cap D_2(N))\in {\mathcal{C}} N \subseteq {\mathcal{C}} M,\end{equation*}

using Theorem 18.

Using the first projection $\pi_1:M\times \Delta_2^*\to M$ , Corollaries 16 and 19 combine to:

\begin{equation*} {\mathcal{C}} M = \left\{\,\pi_1(R\cap (M\times D_2))\,\mid\,R\in {\mathcal{R}}(M\times\Delta_2^*)\,\right\},\qquad\textrm{for any monoid }M.\end{equation*}

We can simplify this further by going from strings in $\Delta_2^*$ to their normal forms in the polycyclic monoid $P_2'\simeq (Q_2^*P_2^*\cup\{0\},\cdot,1)$ where $u\cdot v = \textit{nf}_{2}{uv}$ for $u,v\in Q_2^*P_2^*\cup\{0\}$ ⁷ :

Proposition 20. For any monoid M,

\begin{equation*} {\mathcal{C}} M = \left\{\,\left\{\,m\,\mid\,(m,1)\in R\,\right\}\,\mid\, R \in {\mathcal{R}}(M\times P_2')\,\right\}. \end{equation*}

Proof. Let $\eta:\Delta_2^*\to (\Delta_2\cup\{0\})^*$ be the inclusion homomorphism. Clearly, $\textit{nf}_{2}:(\Delta_2\cup\{0\})^*\to P_2'$ is a homomorphism and surjective since $0=\textit{nf}_{2}({p_0q_1})$ . Therefore, the lifting of $\textit{Id}_M \times (\textit{nf}_{2}\circ\eta):M\times \Delta_2^*\to M\times P_2'$ to the set level is a surjective homomorphism — But the inclusion homomorphism ${\mathcal{R}}(M\times \Delta_2^*)\subseteq {\mathcal{R}}(M\times(\Delta_2\cup\{0\})^*)$ is not surjective!—

\begin{equation*} h:{\mathcal{R}}(M\times \Delta_2^*)\to{\mathcal{R}}(M\times P_2'). \end{equation*}

For $d\in \Delta_2^*$ , $\textit{nf}_{2}(d) = 1$ iff $d\in D_2$ . So if $S\in{\mathcal{R}}(M\times \Delta_2^*)$ and $R\in {\mathcal{R}}(M\times P_2')$ with $R = h(S)$ , then

\begin{equation*} \left\{\,m\,\mid\,(m,1)\in R\,\right\} = \left\{\,m\,\mid\,(m,d)\in S, d\in D_2\,\right\} = \pi_1(S\cap (M\times D_2)). \end{equation*}

Since h is surjective, the claim follows from the above combination of Corollaries 16 and 19.

Intuitively, since each $w\in P_2'$ defines a binary transition relation $\left\{\,(u,v)\,\mid\,u\cdot w = v\,\right\}\subseteq P_2'\times P_2'$ , each $(m,w)\in M \times P_2'$ gives a transition ${\,\stackrel{m}{\Longrightarrow}_{w}\,}$ on $P_2'$ with output in M, via

\begin{equation*} {\,\stackrel{m}{\Longrightarrow}_{w}\,} := \left\{\,(u,m,v)\,\mid\,u\cdot w = v\,\right\} \subseteq P_2'\times M \times P_2'. \end{equation*}

If $(m,w) = (m,\textit{nf}_{2}(d))$ or $(m,w) = (h_M(\alpha),\textit{nf}_{2}({{h_{\Delta_2^*}}(\alpha)}))$ , the same relation is obtained from $(m,d)\in M\times \Delta_2^*$ or $\alpha\in M[\Delta_2]$ . From $R\in {\mathcal{R}}(M\times P_2'),$ an $S\in{\mathcal{R}}(M\times\Delta_2^*)$ with $R=h(S)$ as in the proof above can be obtained by induction on the construction of R, using $S=R$ for R of size 0 or 1, except $S=\emptyset$ for $R=\{(m,0)\}$ . Similarly, when M is finitely generated we can obtain $S\in {\mathcal{R}} M[\Delta_2]$ with $\left\{\,m\,\mid\,(m,1)\in R\,\right\} = h_M(S\cap D_2(M))$ by induction on the construction of R, using $S=\{mw\}$ for $R=\{(m,w)\}$ in the singleton case, except again $S=\emptyset$ for $R=\{(m,0)\}$ .

Since, by Corollary 13, ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ is a quotient of ${\mathcal{R}}(M\times P_2')$ , the above proposition can be used below to show $Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'}) \mathrel{\stackrel{\subset}{{}_\sim}} {\mathcal{C}} M$ .

4.2 Algebraic version of the reverse CST for monoids

To prove an algebraic form of the reverse CST for monoids, i.e. that $Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2')$ embeds into ${\mathcal{C}} M$ , we need to know which elements of ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}}{C_2'}$ belong to the centralizer of $C_2'$ . For this, it is convenient to represent $C_2'$ by $C_2' = {\mathcal{R}} P_2'/\nu$ as in Proposition 9 and to first characterize the elements of $C_2'$ that commute with all generators of $C_2'$ in $C_2'$ , i.e.

\begin{equation*} Z_{\Delta_2}(C_2') := \left\{\,X/\nu \in {\mathcal{R}} P_2'/\nu\,\mid\,\{\delta\}/\nu\cdot X/\nu = X/\nu\cdot \{\delta\}/\nu \textrm{ for each }\delta\in\Delta_2\,\right\}.\end{equation*}

Let I be the set of idempotent elements of $P_2'$ , i.e. the set of those $w\in P_2'$ such that $ww = w$ .

Proposition 21. The set of idempotent elements of $P_2'$ is

\begin{equation*} \left\{\,{\vec{q}}{\vec{p}}\,\mid\,{\vec{q}}\in Q_2^*,{\vec{p}}\in P_2^*, {\vec{p}}{\vec{q}} =1\,\right\} \cup\{0\}. \end{equation*}

Proof. Let $I' := \left\{\,{\vec{q}}{\vec{p}}\,\mid\,{\vec{q}}\in Q_2^*,{\vec{p}}\in P_2^*, {\vec{p}}{\vec{q}} =1\,\right\} \cup\{0\}$ . Clearly, $0 \in I$ . Suppose ${\vec{q}}=q_{i_1}\cdots q_{i_k}\in Q_2^*$ , ${\vec{p}} =p_{j_m}\cdots p_{j_1}\in P_2^*$ and ${\vec{q}}{\vec{p}}\in I'$ . Then, ${\vec{p}}{\vec{q}}=1$ , so ${\vec{q}}{\vec{p}}\cdot {\vec{q}}{\vec{p}} = {\vec{q}}({\vec{p}}{\vec{q}}){\vec{p}} = {\vec{q}}{\vec{p}}$ , so ${\vec{q}}{\vec{p}}\in I$ .

Suppose $w\in P_2' = Q_2^*P_2^*\cup\{0\}$ is idempotent. As $0\in I'$ , we may assume that $w={\vec{q}}{\vec{p}}$ with ${\vec{q}} = q_{i_1}\cdots q_{i_k}\in Q_2^*$ and ${\vec{p}}= p_{j_m}\cdots p_{j_1}\in P_2^*$ for some $k,m\geq 0$ . Suppose $k>m$ . Since $ww=w\not=0$ , we have $p_{j_1}q_{i_1}=1,\ldots,p_{j_m}q_{i_m}=1$ and

\begin{equation*} {\vec{q}}{\vec{p}}{\vec{q}}{\vec{p}} = {\vec{q}} p_{j_m}\cdots p_{j_1}q_{i_1}\cdots q_{i_k}{\vec{p}} = {\vec{q}} q_{i_{m+1}}\cdots q_{i_k}{\vec{p}} = {\vec{q}}{\vec{p}},\end{equation*}

which is impossible. So $k\leq m$ , and by symmetry, $k=m$ . It follows that ${\vec{p}}{\vec{q}} = 1$ ; hence, ${\vec{q}}{\vec{p}}\in I'$ .

Proposition 22. If $R\subseteq P_2'$ satisfies $\{\delta\}R\setminus\{0\} =R\{\delta\}\setminus\{0\}$ , for all $\delta\in \Delta_2$ , then $R\subseteq I$ . If additionally $R\not\subseteq \{0,1\}$ , then $I_0\subseteq R$ or $I_1\subseteq R$ , where

\begin{equation*} I_j := \left\{\,{\vec{q}} q_jp_j{\vec{p}}\,\mid\,{\vec{q}}\in Q_2^*, {\vec{p}}\in P_2^*, {\vec{p}}{\vec{q}}=1\,\right\} \cup\{1\} \quad \textrm{ for $j\in\{0,1\}$}.\end{equation*}

Proof. Clearly, if $R\subseteq\{0,1\}$ , then $R\subseteq I$ . So suppose $w\in R\setminus\{0,1\}$ . By symmetry, we may assume $w\in Q_2^+P_2^*$ , say $w=q_0{\vec{q}}{\vec{p}}'$ for some ${\vec{q}}\in Q_2^*$ and ${\vec{p}}'\in P_2^*$ . Then

\begin{equation*} 0\not= {\vec{q}}{\vec{p}}' = p_0q_0{\vec{q}}{\vec{p}}'\in p_0R\setminus\{0\}\subseteq Rp_0\setminus\{0\},\end{equation*}

so there is $w'\in R$ such that ${\vec{q}}{\vec{p}}'=w'p_0$ . It follows that ${\vec{p}}' = {\vec{p}}p_0$ for some ${\vec{p}}\in P_2^*$ , so $w = q_0{\vec{q}}{\vec{p}} p_0$ . By induction on the length of $w'={\vec{q}}{\vec{p}}\in R\setminus\{0\}$ , it follows that ${\vec{p}}$ is the inverse of ${\vec{q}}$ , so $w'\in I$ and $w\in I$ . Hence, $R\subseteq I$ . We have also seen that when $q_0wp_0\in R$ , then $w\in R$ ; in particular, if $R\not\subseteq\{0\}$ , then $1 \in R$ .

Finally, suppose $w\in R\setminus\{0,1\}$ . By the above argument, we may assume $w = q_jp_j$ with $j\in \{0,1\}$ . For each $i\in\{0,1\}$ , $q_iw \in q_iR\setminus\{0\}\subseteq Rq_i\setminus\{0\}$ ; hence, there is $w'\in R$ with $q_iw = w'q_i$ , and since $w\in Q_2^+P_2^+$ , we must have $w'=q_iwp_i$ . By induction, it follows that $\left\{\,{\vec{q}} w{\vec{p}}\,\mid\,{\vec{q}}\in Q_2^*,{\vec{p}}\in P_2^*,{\vec{p}}{\vec{q}} = 1\,\right\}\subseteq R$ , so $I_j\subseteq R$ .

We next want to see that the infinite sets R with $I_j\subseteq R\subseteq I = I_0\cup I_1\cup \{0\}$ of Proposition 22 are not regular, i.e. do not belong to ${\mathcal{R}} P_2'$ . In order to show, say, $I\notin{\mathcal{R}} P_2'$ , we want to apply a pumping lemma, representing I as the homomorphic image $S/\rho_2$ of some regular set S of the free monoid $(\Delta_2\cup\{0\})^*$ by the monoid congruence

\begin{equation*} \rho_2 = {\left\langle {\left\{\,p_iq_j = \delta_{i,j}\,\mid\,i,j<2\,\right\} \cup \left\{\,x0=0=0x\,\mid\,x\in \Delta_2\cup\{0\}\,\right\}}\right\rangle}.\end{equation*}

But if $w=uv\in S$ is a “long” word with a splitting $w=xyzv$ with $xy^kzv\in S$ for all $k\geq 0$ , the images $\textit{nf}_{2}({xy^kzv})$ of the “pumped strings” $xy^kzv$ need not be outside of I: for example, if $w=u.v=qpqbdq.pp$ with $\textit{nf}_{2}({w})=qqpp \in I$ and $u=x.y.z=qp.qb.dq$ , then for all $k\not=1$ , $\textit{nf}_{2}({xy^kzv}) = 0 \in I$ , since from $pd=0=bq$ we get $\textit{nf}_{2}({xz})=\textit{nf}_{2}({qpdq})= 0$ and $\textit{nf}_{2}({y^2}) = \textit{nf}_{2}({qbqb})=0$ . So a little care is needed to transfer the pumping of S to a pumping of $\textit{nf}_{2}(S)=S/\rho_2$ .

Proposition 23. If $R\in{\mathcal{R}} P_2'$ and $R\subseteq I$ , then R is finite.

Proof. Let $\Delta = \Delta_2\cup\{0\}$ . The polycyclic monoid $P_2'$ is the quotient of the free monoid $\Delta^*$ by the monoid congruence $\rho_2$ above. Since $\cdot/\rho_2 : \Delta^*\to P_2'$ is a surjective homomorphism, every $R\in{\mathcal{R}} P_2'$ is the image under $\cdot/\rho_2$ of some $S\in{\mathcal{R}} \Delta^*$ , i.e. $R=\textit{nf}_{2}(S)=\left\{\,\textit{nf}_{2}(w)\,\mid\,w\in S\,\right\}$ .

We first show that we may assume $R\subseteq S$ . Let

\begin{equation*} {\mathcal{A}}=(A,\langle{\,\stackrel{x}{\longrightarrow}\,}\mid{x\in\Delta\cup\{1\}}\rangle,I^{\mathcal{A}},F^{\mathcal{A}}) \end{equation*}

be a finite automaton over $\Delta$ that recognizes S, with transition relations ${\,\stackrel{x}{\longrightarrow}\,}\subseteq A\times A$ for $x\in\Delta$ and identity relation ${\,\stackrel{1}{\longrightarrow}\,}\subseteq A\times A$ , and sets $I^{\mathcal{A}}\subseteq A$ of initial and $F^{\mathcal{A}}\subseteq A$ of final states. Let

\begin{equation*} {\mathcal{A}}' = (A,\langle{{\,\stackrel{x}{\longrightarrow}\,}'}\mid{x\in\Delta\cup\{1\}}\rangle,I^{\mathcal{A}},F^{\mathcal{A}})\end{equation*}

be the automaton obtained from ${\mathcal{A}}$ by “path-compression,” i.e. the relations ${\,\stackrel{x}{\longrightarrow}\,}'\supseteq {\,\stackrel{x}{\longrightarrow}\,}$ are obtained as follows: for edges $s{\,\stackrel{p_i}{\longrightarrow}\,}t{\,\stackrel{q_i}{\longrightarrow}\,}u$ , $i<2$ , add an edge $s{\,\stackrel{1}{\longrightarrow}\,}u$ , for edges $s{\,\stackrel{x}{\longrightarrow}\,}t{\,\stackrel{1}{\longrightarrow}\,}u$ or $s{\,\stackrel{1}{\longrightarrow}\,}t{\,\stackrel{x}{\longrightarrow}\,}u$ , add an edge $s{\,\stackrel{x}{\longrightarrow}\,}u$ . Likewise, for edges $s{\,\stackrel{p_i}{\longrightarrow}\,}t{\,\stackrel{q_{1-i}}{\longrightarrow}\,}u$ , $i<2$ , add an edge $s{\,\stackrel{0}{\longrightarrow}\,}u$ , and for edges $s{\,\stackrel{x}{\longrightarrow}\,}t{\,\stackrel{0}{\longrightarrow}\,}u$ or $s{\,\stackrel{0}{\longrightarrow}\,}t{\,\stackrel{x}{\longrightarrow}\,}u$ add $s{\,\stackrel{0}{\longrightarrow}\,}u$ . Let $S'\in{\mathcal{R}}{\Delta^*}$ be the set recognized by ${\mathcal{A}}'$ . As each accepting path of ${\mathcal{A}}'$ is the compression of an accepting path of ${\mathcal{A}}$ , we have $S\subseteq S'$ , and as their labellings have the same normal form, $\textit{nf}_{2}(S')=\textit{nf}_{2}(S)=R$ . Since for each ${\vec{q}}{\vec{p}}\in R$ there is some $w\in S$ with $\textit{nf}_{2}(w)={\vec{q}}{\vec{p}}$ , there is an accepting path in ${\mathcal{A}}'$ labeled by ${\vec{q}}{\vec{p}}$ , likewise for $0\in R$ , so $R\subseteq S'$ . Henceforth, we assume $S=S'$ and ${\mathcal{A}}={\mathcal{A}}'$ .

We can now show that R cannot be infinite, by applying the pumping lemma. Let m be the number of states of an automaton ${\mathcal{A}}$ recognizing a set $S\in {\mathcal{R}} \Delta^*$ with $\textit{nf}_{2}(S) = R\subseteq S$ . Suppose $R\subseteq I$ is infinite. Then there is ${\vec{q}}{\vec{p}} \in R\subseteq S$ with $|{\vec{q}}| > m$ , ${\vec{q}}\in Q_2^*$ , ${\vec{p}}\in P_2^*$ and ${\vec{p}}{\vec{q}}=1$ . Since ${\mathcal{A}}$ has an accepting path labeled ${\vec{q}}{\vec{p}}$ and $m>|{\vec{q}}|$ , by the pumping lemma for S there is a splitting ${\vec{q}}=xyz$ with $x,y,z\in Q_2^*$ with $0 < |y|\leq m$ such that $xy^kz{\vec{p}} \in S$ for all $k\geq 0$ . But since $xz\in Q_2^*$ , ${\vec{p}}\in P_2^*$ and $xz{\vec{p}}\in S$ , we have $\textit{nf}_{2}({xz{\vec{p}}})=xz{\vec{p}}$ (and $\not=0$ ), which is impossible since $|xz|<|{\vec{q}}|=|{\vec{p}}|$ and $\textit{nf}_{2}(S)=R\subseteq I$ . It follows that R cannot be infinite.

When using $C_2' \simeq {\mathcal{R}} P_2'/\nu$ according to Proposition 9, we write 0’ and l’ for the neutral elements of $+$ and $\cdot$ in $C_2'$ , respectively, to distinguish them from the elements 0 and 1 of $P_2'$ . The following lemmata characterize the elements of the centralizer of $C_2'$ in $C_2'$ and in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ , respectively:

Lemma 24. $Z_{C_2'}(C_2')=\{{0'},{l'}\}=Z_{\Delta_2}(C_2')$ .

Proof. $\{{0'},{l'}\}\subseteq Z_{C_2'}(C_2')\subseteq Z_{P_2'}(C_2')\subseteq Z_{\Delta_2}(C_2')$ : Clearly, ${0'} = \emptyset/\nu=\{0\}/\nu$ and ${l'}= \{1\}/\nu=\{0,1\}/\nu$ commute with $R/\nu$ for every $R\in {\mathcal{R}} P_2'$ . The other two inclusions follow from the representations of $w\in P_2'$ and $\delta\in\Delta_2$ in $C_2'$ by $\{w\}/\nu$ and $\{\delta\}/\nu$ .

$Z_{\Delta_2}(C_2') \subseteq \{{0'}, {l'}\}$ : Suppose $R\in{\mathcal{R}} P_2'$ and $R/\nu$ commutes with $\{\delta\}/\nu$ for every $\delta\in\Delta_2$ . Then, by Proposition 9, $\{\delta\}R\setminus\{0\}=R\{\delta\}\setminus\{0\}$ for every $\delta\in\Delta_2$ , so $R\subseteq I$ by Proposition 4.2, then R is finite by Proposition 23, and so by Proposition 22 again, $R\subseteq \{0,1\}$ . It follows that $R/\nu = \emptyset/\nu =\{0\}/\nu=0'$ or $R/\nu = \{1\}/\nu = \{0,1\}/\nu=1'$ ; hence, $Z_{\Delta_2}(C_2')\subseteq \{{0'},{l'}\}$ .

Lemma 25. $ Z_{C_2'}({\mathcal{R}} M \mathop{\otimes_{\mathcal{R}}} {C_2'}) = \left\{\,[R]\,\mid\,R\in {\mathcal{R}}({\mathcal{R}} M\times C_2'), R \subseteq {\mathcal{R}} M\times \{{0'},{l'}\}\,\right\}.$

Proof. $\supseteq$ : For each $c\in C_2'$ , $cb=bc$ for $b\in \{{0'},{l'}\}$ , so by ${\mathcal{R}}$ -distributivity,

\begin{eqnarray*} (\{1\}\otimes c)[R] &=& (\{1\}\otimes c)\sum\left\{\,A\otimes b\,\mid\,(A,b)\in R\,\right\}\\ &=& \left(\sum\left\{\,A\otimes b\,\mid\,(A,b)\in R\,\right\}\right)(\{1\}\otimes c)= [R](\{1\}\otimes c).\end{eqnarray*}

$\subseteq$ : Every element of ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} {C_2'}$ is of the form $[R_\nu]$ with $R\in {\mathcal{R}}({\mathcal{R}} M\times {\mathcal{R}} P_2')$ and $R_\nu =\left\{\,(A,B/\nu)\,\mid\,(A,B)\in R\,\right\}$ . The isomorphism

\begin{equation*} {\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2' \simeq {\mathcal{R}}(M\times P_2')/{\tilde\nu} \end{equation*}

of Corollary 13 maps $[R_\nu]$ to $(S_R)/{\tilde\nu}$ , where $S_R = \bigcup\left\{\,A\times B\,\mid\,(A,B)\in R\,\right\}$ . Suppose $[R_\nu]\in Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2')$ . Then for every $w\in P_2'\setminus\{0\}$ , $[R_\nu]$ commutes with $[T_\nu]$ for $T=\{(\{1\},\{w\})\}$ , so the image $(S_R)/{\tilde\nu}$ of $[R_\nu]$ commutes with the image $(S_T)/{\tilde\nu} = \{(1,w)\}/{\tilde\nu}$ of $[T_\nu]$ . Therefore, $(S_R)/{\tilde\nu}\in Z_{P_2'}({\mathcal{R}}(M\times P_2')/{\tilde\nu})$ . In particular, $(S_R)/{\tilde\nu} \in Z_{\Delta_2}({\mathcal{R}}(M\times P_2')/{\tilde\nu})$ , which is equivalent to

\begin{equation*} \{(1,\delta)\}S_R \setminus (M\times\{0\}) = S_R\{(1,\delta)\} \setminus (M\times\{0\}), \quad\textrm{for all }\delta\in\Delta_2.\end{equation*}

Let $X\in {\mathcal{R}} P_2'$ be the second projection of $S_R\in {\mathcal{R}}(M\times P_2')$ . Then

\begin{equation*} \{\delta\}X\setminus \{0\} = X\{\delta\} \setminus \{0\}, \quad\textrm{for all }\delta\in\Delta_2,\end{equation*}

i.e. $X/\nu\in Z_{\Delta_2}(C_2')$ , and by the proof of Lemma 24, $X\subseteq \{0,1\}$ ; hence, $S_R\subseteq M\times\{0,1\}$ . So for $(A,B)\in R$ , $B\subseteq \{0,1\}$ , which implies $R_\nu\subseteq {\mathcal{R}} M \times \{{0'},{l'}\}$ .

We can now prove the algebraic form of the reverse CST for monoids:

Theorem 26 (Algebraic reverse CST for monoids). For any monoid M and $R\in {\mathcal{R}}({\mathcal{R}} M\times C_2')$ ,

\begin{equation*} \bigcup\left\{\,A\,\mid\,(A,{l'})\in R\,\right\} \in {\mathcal{C}} M. \end{equation*}

In fact, there is an injective, monotone map ${}^\vee:Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2')\to{\mathcal{C}}M$ defined by

\begin{equation*} [R] \mapsto [R]^\vee := \bigcup\left\{\,A\,\mid\,(A,{l'})\in R\,\right\} \quad\textrm{ for }R\in{\mathcal{R}}({\mathcal{R}} M\times C_2').\end{equation*}

Proof. We switch the notation and use $[R_\nu]$ for the [R] of the statement above, where

\begin{equation*} R_\nu =\left\{\,(A,B/\nu)\,\mid\,(A,B)\in R\,\right\}\in {\mathcal{R}}({\mathcal{R}} M\times C_2') \end{equation*}

for some $R\in {\mathcal{R}}({\mathcal{R}} M\times {\mathcal{R}} P_2')$ . For these R, put

\begin{equation*} L_R := \bigcup\left\{\,A\,\mid\,(A,B)\in R, 1\in B\,\right\}. \end{equation*}

By Lemma 25, if $[R_\nu]\in Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2')$ , then $R_\nu\subseteq {\mathcal{R}} M\times\{{0'},{l'}\}$ and $R\subseteq {\mathcal{R}} M\times {\mathcal{P}}\{0,1\}$ .

Claim 1. The map $\cdot^\vee : Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2') \to {\mathcal{P}} M$ , given by

\begin{eqnarray*} [R_\nu]^\vee &=& \bigcup\left\{\,A\,\mid\,(A,{l'})\in R_\nu\,\right\}\end{eqnarray*}

for $R\in {\mathcal{R}}({\mathcal{R}} M\times {\mathcal{R}} P_2')$ , is well-defined and has values in ${\mathcal{C}} M$ .

Proof of Claim 1. Clearly, $\bigcup\left\{\,A\,\mid\,(A,1')\in R_\nu\,\right\} = L_R$ . Suppose there is $T\in{\mathcal{R}}({\mathcal{R}} M\times {\mathcal{R}} P_2')$ with $[R_\nu] = [T_\nu]$ . By the isomorphism $[R_\nu] \mapsto (S_R)/{\tilde\nu}$ of Corollary 13, $(S_R)/{\tilde\nu} = (S_T)/{\tilde\nu}$ ; hence,

\begin{equation*} S_R\setminus (M\times\{0\}) = S_T\setminus (M\times\{0\}). \end{equation*}

Therefore, using the fact that $S_R, T_R \subseteq M\times\{0,1\}$ ,

\begin{eqnarray*} L_R &=& \bigcup\left\{\,A\,\mid\,(A,B)\in R, 1\in B\,\right\}\\ &=& \left\{\,m\,\mid\,(A,B)\in R, (m,1)\in A\times B\,\right\}\\ &=& \left\{\,m\,\mid\,(m,1)\in S_R\,\right\}\\ &=& \left\{\,m\,\mid\,(m,w)\in S_R\setminus (M\times\{0\}), w\in P_2'\,\right\}\\ &=& \left\{\,m\,\mid\,(m,w)\in S_T\setminus (M\times\{0\}), w\in P_2'\,\right\}\\ &=& L_T.\end{eqnarray*}

It follows that $\bigcup\left\{\,A\,\mid\,(A,1')\in R_\nu\,\right\} = L_R = L_T =\bigcup\left\{\,A\,\mid\,(A,1')\in T_\nu\,\right\}$ , and $\cdot^\vee$ is well-defined. Since $L_R = \left\{\,m\,\mid\,(m,1)\in S_R\,\right\}$ for $S_R\in {\mathcal{R}}(M\times P_2')$ , we have $L_R\in {\mathcal{C}} M$ by Proposition 20. $\triangleleft$

Claim 2. The map $\cdot^\vee : Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2')\to {\mathcal{C}} M$ is injective.

Proof of Claim 2. We show that the map $\widehat{\,\cdot\,}: {\mathcal{C}} M\to Z_{C_2'}({\mathcal{R}} M \mathop{\otimes_{\mathcal{R}}} {C_2'})$ of Theorem 17 is an inverse to $\cdot^\vee$ . It maps $[R_\nu]^\vee=L_R \in{\mathcal{C}} M$ back to $[R_\nu]$ , because

\begin{eqnarray*} \widehat{[R_\nu]^\vee} &=& \widehat{L_R} = \sum\left\{\,\{m\}\otimes {l'}\,\mid\,m\in L_R\,\right\}\\ &=& \sum\left\{\,A\otimes {l'}\,\mid\,(A,B)\in R, 1\in B\,\right\}\\ &=& \sum\left\{\,A\otimes {l'}\,\mid\,(A,{l'})\in R_\nu\,\right\}\\ &=& [R_\nu]\end{eqnarray*}

since $R_\nu\subseteq {\mathcal{R}}({\mathcal{R}} M\times\{{0'},{l'}\})$ and $A\otimes {0'} = 0$ . $\triangleleft$

Claim 3. The map $\cdot^\vee : Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2')\to {\mathcal{C}} M$ is monotone.

Proof of Claim 3. Suppose $R,S\in{\mathcal{R}}({\mathcal{R}} M \times {\mathcal{R}} P_2')$ such that $[R_\nu], [S_\nu] \in Z_{C_2'}({\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2')$ and $[R_\nu]\leq [S_\nu]$ . By the definition of $\leq$ on ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ , $[R_\nu \cup S_\nu] = [S_\nu]$ ; hence with Claim 1,

\begin{equation*} [R_\nu]^\vee \subseteq \bigcup\left\{\,A\,\mid\,(A,1')\in R_\nu\cup S_\nu\,\right\} = \bigcup\left\{\,A\,\mid\,(A,1')\in S_\nu\,\right\} = [S_\nu]^\vee,\end{equation*}

so $\ \cdot^\vee$ is monotone. $\triangleleft$

5. Algebraic Representation of the ${\mathcal{C}}$ -Closure ${\mathcal{C}} M$ of ${\mathcal{R}} M$

We can now prove our first main result, which combines the algebraic Chomsky–Schützenberger theorem for monoids M and its reverse, Theorems 17 and 26, to an algebraic representation of the $\mu$ -continuous Chomsky algebra ${\mathcal{C}} M$ in the ${}^*$ -continuous Kleene algebra ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}}{C_2'}$ :

Theorem 27. For any monoid M, $Z_{C_2'}({\mathcal{R}} M \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is a ${\mathcal{C}}$ -dioid, and the maps

\begin{equation*} {\widehat{\,\cdot\,}} : {{\mathcal{C}} M} \rightleftarrows {Z_{C_2'}({\mathcal{R}} M \mathop{\otimes_{\mathcal{R}}} {C_2'})} : {\cdot^\vee} \end{equation*}

form a ${\mathcal{C}}$ -isomorphism, where for $L\in{\mathcal{C}} M$ and $R \in {\mathcal{R}}({\mathcal{R}} M\times C_2')$ with $[R]\in Z_{C_2'}({\mathcal{R}} M \mathop{\otimes_{\mathcal{R}}} {C_2'})$ ,

\begin{equation*} \widehat L := \sum\left\{\,\{m\}\otimes{l'}\,\mid\,m\in L\,\right\} \quad\textrm{and}\quad [R]^\vee := \bigcup\left\{\,A\,\mid\,(A,{l'})\in R\,\right\}.\end{equation*}

Proof. We use $D := Z_{C_2'}({\mathcal{R}} M \mathop{\otimes_{\mathcal{R}}} {C_2'})$ to simplify the notation.

Claim 1. The maps $\,\cdot^\vee:D\to{\mathcal{C}} M$ and $\widehat{\,\cdot\,}:{\mathcal{C}} M\to D$ are inverse to each other.

Proof of Claim 1. In the proof of Theorem 17, we already showed that $\widehat{\,\cdot\,}$ is an inverse of ${\cdot}^\vee$ . For $L\in {\mathcal{C}} M,$ there is $R\in {\mathcal{R}}({\mathcal{R}} M\times {\mathcal{R}} P_2')$ with $R_\nu\subseteq {\mathcal{R}}M\times\{{0'},{l'}\}$ and $\widehat L=[R_\nu]$ ; hence,

\begin{equation*} (\widehat L)^\vee = \left(\sum\left\{\,\{m\}\otimes {l'}\,\mid\,m\in L\,\right\}\right)^\vee = [R_\nu]^\vee =\bigcup\left\{\,A\,\mid\,(A,{l'})\in R_\nu\,\right\} = L_R.\end{equation*}

By applying $\widehat{\,\cdot\,}$ , we get $\widehat L = \widehat{L_R}$ , and since $\widehat{\,\cdot\,}$ is injective by Theorem 17, $(\widehat L)^\vee = L_R =L$ . $\triangleleft$

It remains to be shown that the bijection between ${\mathcal{C}} M$ and D given by the maps $\widehat{\,\cdot\,}$ and $\cdot^\vee$ is a ${\mathcal{C}}$ -isomorphism.

Claim 2. The maps $\,{\widehat{\cdot}\,} : {{\mathcal{C}} M} \rightleftarrows {D} : {{\cdot\,}^\vee}$ are monotone homomorphisms.

Proof of Claim 2. Obviously, $\widehat{\,\cdot\,}$ is monotone; the monotonicity of $\cdot^\vee$ is noted in Theorem 17.

1. The map $\cdot^\vee: D\to {\mathcal{C}} M$ is a homomorphism: first,

\begin{equation*} 1^\vee = (\{1\}\otimes {l'})^\vee = [\{(\{1\},{l'})\}]^\vee = \{1\}, \end{equation*}

and, second, for $[R],[S] \in D$ represented by $R,S\in {\mathcal{R}}({\mathcal{R}}M\times C_2')$ with $R,S\subseteq {\mathcal{R}} M\times \{{0'},{l'}\}$ ,

\begin{eqnarray*} ([R]\cdot [S])^\vee &=& [RS]^\vee\\ &=& \bigcup\left\{\,C\,\mid\,(C,{l'})\in RS\,\right\}\\ &=& \bigcup\left\{\,AB\,\mid\,(A,{l'})\in R, (B,{l'})\in S\,\right\}\\ &=& \bigcup\left\{\,A\,\mid\,(A,{l'})\in R\,\right\}\cdot \bigcup\left\{\,B\,\mid\,(B,{l'})\in S\,\right\}\\ &=& [R]^\vee\cdot [S]^\vee,\end{eqnarray*}

because $(C,{l'})=(A,a)(B,b)$ iff $AB=C$ and $a={l'}=b$ , since $a,b\in\{{0'},{l'}\}$ .

2. The map $\widehat{\,\cdot\,} : {\mathcal{C}} M\to D$ is a homomorphism: clearly $\widehat{\{1\}} = \{1\}\otimes {l'} = 1$ , and for $L_1,L_2\in {\mathcal{C}} M$ , since $\cdot^\vee$ is a homomorphism and inverse to $\widehat{\,\cdot\,}$ by Claim 3.1, we have

\begin{equation*} (\widehat L_1\cdot\widehat L_2)^\vee = (\widehat L_1)^\vee \cdot(\widehat L_2)^\vee =L_1\cdot L_2 =\widehat{L_1\cdot L_2}^\vee;\end{equation*}

by the injectivity of ${\cdot}^\vee$ , we get $ \widehat L_1\cdot\widehat L_2 = \widehat{L_1\cdot L_2}.$ $\triangleleft$

Claim 3. D is a ${\mathcal{C}}$ -dioid.

Proof of Claim 3. By Theorem 17, for $L\in {\mathcal{C}} M$ , $\widehat{L} = \sum\left\{\,\{m\}\otimes 1'\,\mid\,m\in L\,\right\}$ is the least upper bound of the image $\widetilde f(L)$ of L under the homomorphism $f:M\to D$ given by $f(m) = \{m\}\otimes 1'$ . By the previous claims, $\widehat{\,\cdot\,}:{\mathcal{C}} M\to D$ is a surjective homomorphism. By Proposition 14, D is an ${\mathcal{R}}$ -dioid; hence, a dioid, and so by Lemma 3, D is a ${\mathcal{C}}$ -dioid. $\triangleleft$

Claim 4. $\widehat{\,\cdot\,}:{\mathcal{C}} M\to D$ and $\,\cdot^\vee : D \to {\mathcal{C}} M$ are ${\mathcal{C}}$ -morphisms.

Proof of Claim 4. Since $\widehat{\,\cdot\,}$ is a homomorphism, so is ${\mathcal{C}}(\widehat{\,\cdot\,}):{\mathcal{C}}{\mathcal{C}}M\to {\mathcal{C}} D$ . Hence for $U\in {\mathcal{C}}{\mathcal{C}} M$ , $\left\{\,\widehat L\,\mid\,L\in U\,\right\}\in {\mathcal{C}}D$ , and by the proof of Lemma 3, its least upper bound is $\sum\left\{\,\widehat L\,\mid\,L\in U\,\right\} = \widehat{\bigcup U}$ . Since $\widehat{\,\cdot\,}$ is a monotone homomorphism, this shows that $\widehat{\,\cdot\,}$ is a ${\mathcal{C}}$ -morphism. $\triangleleft$

For $\,\cdot^\vee$ , for each $V\in {\mathcal{C}} D$ there is $U\in {\mathcal{C}}{\mathcal{C}} M$ such that $V=\left\{\,\widehat L\,\mid\,L\in U\,\right\}$ and $\sum V = \widehat{\bigcup U}$ . Hence, since $\,{\widehat{\,\cdot\,}} : {{\mathcal{C}} M} \rightleftarrows {D} : {\,\cdot^\vee}\,$ is a bijection, $(\widehat L)^\vee = L$ for each $L\in {\mathcal{C}} M$ . With $\bigcup U\in {\mathcal{C}} M$ , it follows that

\begin{equation*} \left(\sum V\right)^\vee = \left(\widehat{\bigcup U}\right)^\vee = \bigcup U = \bigcup\left\{\,{\widehat L}^\vee\,\mid\,L\in U\,\right\} = \bigcup\left\{\,v^\vee\,\mid\,v\in V\,\right\}.\end{equation*}

As $\cdot^\vee$ is a monotone homomorphism, this shows that it is a ${\mathcal{C}}$ -morphism. $\triangleleft$

Before considering an algebraic representation of the fixed-point closure of an arbitrary ${\mathcal{R}}$ -dioid K, we remark that the case $K={\mathcal{R}} M$ treated so far is sufficient to provide a semantics to regular expression tools for context-free languages, like the one proposed by Hopkins (2007).

The results proven for $n=2$ hold as well for $n>2$ , which is convenient to treat ${\langle{0}\!\mid}, {\langle{0}\!\mid}$ as a fresh, unused pair of brackets. If X is a finite set disjoint from $\Delta_n$ , all regular expressions over $X\cup\Delta_n$ have an interpretation in ${\mathcal{R}} X^*\mathop{\otimes_{\mathcal{R}}} C_n'$ . Using the tensor product embeddings, atoms $x\in X$ are interpreted by $\{x\}\otimes1$ and atoms $\delta\in\Delta_n$ by $\{1\}\otimes \{\delta\}/\rho_n$ , as in Example 5. A subset of the regular expressions over $X\cup\Delta_n$ that are sufficient to name all context-free sets of ${\mathcal{C}}X^*\simeq Z_{C_n'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_n'})$ is easily selected as follows.

Corollary 28. For $n>2$ , an element $e\in {\mathcal{R}} X^*\mathop{\otimes_{\mathcal{R}}} {C_n'}$ belongs to $Z_{C_n'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_n'})$ iff e is the value of a regular expression ${\langle{0}\!\mid}r{\mid\!{0}\rangle}$ over $X\cup\Delta_n$ where ${\langle{0}\!\mid}$ and ${\langle{0}\!\mid}$ do not occur in r.

Proof. $\Rightarrow$ : Suppose $e \in Z_{C_n'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_n'})$ . By Theorem 27, there is $L \in {\mathcal{C}} X^*$ with $L = e^\vee$ . Let

\begin{equation*} y_1 \geq p_1, \ldots, y_k \geq p_k \end{equation*}

be a context-free grammar for L, i.e. L is the first component $L_1$ of its least solution $L_1,\ldots,L_k \in {\mathcal{C}} X^*$ . Construct the right-linear grammar

\begin{equation*} y_1 \geq p_1'', \ldots, p_k\geq p_k'',\quad y_1^F \geq p_1^F + 1,\quad y_2^F\geq p_2^F, \ldots, y_k^F\geq p_k^F \end{equation*}

as in the proof of Theorem 15. We can assume that ${\langle{1}\!\mid},\ldots,{\langle{n}\!\mid},{\mid\!{1}\rangle},\ldots, {\mid\!{n}\rangle}$ are sufficient to wrap each occurrence of a variable $y_1,\ldots,y_k$ in $p_1,\ldots, p_k$ by a different bracket pair ${\langle{i}\!\mid}, {\mid\!{i}\rangle}$ , otherwise use the two pairs ${\langle{1}\!\mid},{\mid\!{1}\rangle}$ and ${\langle{2}\!\mid},{\mid\!{2}\rangle}$ to encode new bracket pairs. Let r be the regular expression over $X\cup\Delta_n$ for the least solution in $y_1$ of the right-linear grammar; r does not contain ${\langle{0}\!\mid}$ and ${\langle{0}\!\mid}$ . The corresponding regular set $R\in {\mathcal{R}}(X^*[\Delta_n])$ satisfies $L = h_{X^*}(R\cap D_n(X))$ , and the value of ${\langle{0}\!\mid} r{\langle{0}\!\mid}$ in ${\mathcal{R}} X^*\mathop{\otimes_{\mathcal{R}}} C_2'$ is $e=\widehat L \in Z_{C_n'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_n'})$ . We can see ${\langle{0}\!\mid} r{\langle{0}\!\mid}$ as the solution term for $\widehat y$ of the right-linear grammar

\begin{equation*} \widehat y \geq {\langle{0}\!\mid} y_1,\quad y_1 \geq p_1'', \ldots, y_k''\geq p_k'', 1^F\geq p_1^F + {\langle{0}\!\mid},\quad y_2^F\geq p_2^F,\ldots, y_k^F\geq p_k^F. \end{equation*}

(Cf. the automata in Example 6.)

$\Leftarrow$ : Let r be a regular expression over $X\cup\Delta_n$ not containing ${\langle{0}\!\mid},{\langle{0}\!\mid}$ . By Corollary 13,

\begin{equation*} {\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2' \simeq {\mathcal{R}} X^* \mathop{\otimes_{\mathcal{R}}} ({\mathcal{R}} P_n'/\nu) \simeq {\mathcal{R}}(X^*\times P_n')/{\tilde\nu}, \end{equation*}

where $\tilde\nu$ is the ${\mathcal{R}}$ -congruence generated by $\{(1,0)\}=\emptyset$ . So the value of r in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ can be represented by $T/\tilde\nu$ with $T\in {\mathcal{R}}(X^*\times P_n')$ . By the choice of r, for no $(m,w)\in T$ do ${\langle{0}\!\mid}$ or ${\langle{0}\!\mid}$ occur in its second component $w\in P_n'=Q_n^*P_n^*\cup\{0\}$ . So the value of ${\langle{0}\!\mid} r{\langle{0}\!\mid}$ is $S/\tilde\nu$ for $S=\{(1,{\langle{0}\!\mid})\}T\{(1,{\langle{0}\!\mid})\}$ , and $S\subseteq X^*\times \{0,1\}$ due to bracket mismatches in the second components. The isomorphisms of Theorem 12 and Proposition 9 map $S/\tilde\nu$ to some $[R]\in {\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ with $R\subseteq {\mathcal{R}} X^*\times\{0',1'\}$ . By Lemma 25, the value [R] of ${\langle{0}\!\mid}r{\langle{0}\!\mid}$ belongs to the centralizer of $C_n'$ .

Notice that regular combinations of expressions of the above form ${\langle{0}\!\mid} r{\langle{0}\!\mid}$ are no longer of this form, but of course also denote sets in ${\mathcal{C}} X^*$ .

There is another way to find, for $L\in {\mathcal{C}} X^*$ , a regular expression r such that ${\langle{0}\!\mid} r{\langle{0}\!\mid}$ evaluates to $\widehat L$ in ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}}{C_n'}$ , which is perhaps more appealing than the one in the proof above: a non-deterministic bottom-up, top-down or Earley parser (cf. Sikkel 1998) for a context-free grammar $G=(X,Y,P,S)$ for L is an iterative program, i.e. a regular expression r over an alphabet of basic commands. Suppose that $\Delta_n$ contains, besides ${\langle{0}\!\mid}$ and ${\langle{0}\!\mid}$ , an opening bracket ${\langle{z}\!\mid}$ and a closing bracket ${\mid\!{z}\rangle}$ for each $z\in X\cup Y$ . The bottom-up parser, for example, can then be expressed by

\begin{equation*} r = \left(\sum\left\{\,\textit{shift}_x\,\mid\,x\in X\,\right\} +\sum\left\{\,\textit{reduce}_{(A,\alpha)}\,\mid\,(A,\alpha)\in P\,\right\}\right)^*\end{equation*}

with $\textit{shift}_x = x{\langle{x}\!\mid}$ and $\textit{reduce}_{(A,\alpha)}={\mid\!{\alpha}\rangle}{\langle{A}\!\mid}$ , where ${\mid\!{z_1\ldots z_k}\rangle}={\mid\!{z_k}\rangle}\ldots{\mid\!{z_1}\rangle}$ for $z_i\in X\cup Y$ . Then, $\widehat{L} = \sum\left\{\,\{m\}\otimes 1\,\mid\,m\in L\,\right\}= {\langle{0}\!\mid} r{\mid\!{S}\rangle}{\langle{0}\!\mid}$ . If G is the grammar of Example 6, the word baac is accepted by the shift-reduce sequence

\begin{equation*} \textit{shift}_b;\;\textit{shift}_a;\;\textit{reduce}_{(y,a)};\;\textit{shift}_a;\;\textit{reduce}_{(y,a)};\; \textit{reduce}_{(z,yy)};\;\textit{shift}_c;\;\textit{reduce}_{(y,bzc)};\end{equation*}

its value in ${\mathcal{R}} X^*\mathop{\otimes_{\mathcal{R}}}{C_n'}$ is $\{baac\}\otimes\{{\langle{y}\!\mid}\}$ , and since y was the start symbol S, $\{baac\}\otimes 1 \leq {\langle{0}\!\mid}r{\mid\!{S}\rangle}{\langle{0}\!\mid}= \widehat L$ . This indicates that ${\mathcal{R}} X^*\mathop{\otimes_{\mathcal{R}}} C_2'$ may be useful to study parsing algebraically.

6. Algebraic Representation of the $\mathbb{\mathcal{C}}$ -Closure of an Arbitrary ${\mathcal{R}}$ -Dioid K

We can now generalize Theorem 27, the algebraic representation of the ${\mathcal{C}}$ -closure of ${\mathcal{R}}$ -dioids ${\mathcal{R}} M$ with monoid M to an algebraic construction of the ${\mathcal{C}}$ -closure ${Q_{\mathcal{R}}^{\mathcal{C}}} : {\mathbb{D}}{\mathcal{R}}\to {\mathbb{D}}{\mathcal{C}}$ on the Eilenberg-Moore category ${\mathbb{D}}{\mathcal{R}}$ of all ${\mathcal{R}}$ -dioids. We need a series of steps.

Lemma 29. For any ${\mathcal{R}}$ -dioid K,

\begin{equation*} {\mathcal{C}} K = \left\{\,\left\{\,m\,\mid\,(m,1)\in R\,\right\}\,\mid\,R\in {\mathcal{R}}(K\times C_2'), R\subseteq K\times\{0,1\}\,\right\}.\end{equation*}

Proof. $\subseteq$ : For $\Delta_2=\{p_0,q_0,p_1,q_1\}$ , let $\rho_2$ be the ${\mathcal{R}}$ -congruence on ${\mathcal{R}}\Delta_2^*$ generated by the semiring equations

\begin{equation*} p_iq_j=\delta_{i,j}, \quad 0\leq i,j\leq 1, \end{equation*}

and $\cdot/\rho_2 : {\mathcal{R}}\Delta_2^*\to C_2' = {\mathcal{R}}\Delta_2^*/\rho_2$ the canonical ${\mathcal{R}}$ -morphism. By Corollary 16 there is a set $S\in{\mathcal{R}}(M\times\Delta_2^*)$ such that

\begin{equation*} L = \left\{\,m\,\mid\,(m,d)\in S, d\in D_2\,\right\}, \end{equation*}

and for each $(m,d)\in S$ ,

(12) \begin{equation} \{d\}/\rho_2 = \begin{cases} 1 & d\in D_2,\\ 0, & d\notin D_2.\end{cases}\end{equation}

The isomorphism ${\mathcal{R}}(K\times\Delta_2^*)\simeq {\mathcal{R}} K\mathop{\otimes_{\mathcal{R}}} {\mathcal{R}}\Delta_2^*$ of Proposition 11 maps S to $[R_S]$ , where

\begin{equation*} R_S = \left\{\,(\{m\},\{d\})\,\mid\,(m,d)\in S\,\right\} \in {\mathcal{R}}({\mathcal{R}} K\times {\mathcal{R}}\Delta_2^*). \end{equation*}

The lifting of the homomorphism $\sum\times(\cdot/\rho_2) : {\mathcal{R}} K\times {\mathcal{R}}\Delta_2^* \to K \times C_2'$ , maps $R_S$ to

\begin{equation*} R := \left\{\,(m,\{d\}/\rho_2)\,\mid\,(m,d)\in S\,\right\} \in {\mathcal{R}}(K\times C_2').\end{equation*}

By (12), R is a subset of $K\times \{0,1\}$ such that

\begin{equation*} L = \left\{\,m\,\mid\,(m,d)\in S, d\in D_2\,\right\} = \left\{\,m\,\mid\,(m,1)\in R\,\right\}.\end{equation*}

$\supseteq$ : Suppose $R\in {\mathcal{R}}(K\times C_2')$ and $R\subseteq K\times\{0,1\}$ . Then for $R'=\left\{\,(\{m\},c)\,\mid\,(m,c)\in R\,\right\}$ , we have $R'\in {\mathcal{R}}({\mathcal{R}} K\times C_2')$ and $R'\subseteq {\mathcal{R}} K\times \{0,1\}$ , so $[R']\in Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ by Lemma 25; hence,

\begin{equation*} \left\{\,m\,\mid\,(m,1)\in R\,\right\} = \bigcup\left\{\,A\,\mid\,(A,1)\in R'\,\right\} = [R']^\vee \in {\mathcal{C}} K.\end{equation*}

by Theorem 26.

Since for $L\in{\mathcal{C}} K$ , $\widetilde{\top_1}(L)=\left\{\,m\otimes 1\,\mid\,m\in L\,\right\}\in{\mathcal{C}}(Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}))$ , the next lemma is a step towards the ${\mathcal{C}}$ -completeness of $Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ .

Lemma 30. For each ${\mathcal{R}}$ -dioid K, there is a surjective homomorphism

\begin{equation*}\widehat{\,\cdot\,} : {\mathcal{C}} K \to Z_{C_{2}'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}),\end{equation*}

that assigns to each $L\in {\mathcal{C}} K$ a least upper bound of $\widetilde{\top_1}(L)$ in $K\mathop{\otimes_{\mathcal{R}}} C_2'$ ,

\begin{equation*} \widehat{\,L\,} = \sum\widetilde{\top_1}(L) = \sum\left\{\,m\otimes 1\,\mid\,m\in L\,\right\}. \end{equation*}

Proof. For each $L\in{\mathcal{C}} K,$ there is, by Lemma 29, a set $R\in {\mathcal{R}}(K\times C_2')$ with $R\subseteq K\times\{0,1\}$ and $L=\left\{\,m\,\mid\,(m,1)\in R\,\right\}$ . As $m\otimes 0 = 0$ for all $m\in K$ , it follows that

\begin{equation*} [R] = \sum\left\{\,m\otimes d\,\mid\,(m,d)\in R\,\right\} = \sum\left\{\,m\otimes 1\,\mid\,(m,1)\in R\,\right\},\end{equation*}

showing that $\widetilde{\top_1}(L)=\left\{\,m\otimes 1\,\mid\,m\in L\,\right\}$ has a least upper bound in $K\mathop{\otimes_{\mathcal{R}}} C_2'$ , namely

\begin{equation*} \widehat L := \sum\left\{\,m\otimes 1\,\mid\,m\in L\,\right\} = [R].\end{equation*}

Since all $m\otimes d$ with $(m,d)\in R$ belong to $Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ , we have $[R]\in Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ by Proposition 14. This defines a map $\widehat\cdot:{\mathcal{C}} K\to Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ .

The map $\widehat{\,\cdot\,}$ is a homomorphism: $\widehat{\{1\}} =\sum\{1\otimes 1\}=1\otimes 1 = 1$ and for $L_1,L_2\in{\mathcal{C}} K$ , by Lemma 29 there are $R_1,R_2\in{\mathcal{R}}(K\times C_2')$ such that $R_i\subseteq K\times\{0,1\}$ and $L_i=\left\{\,m\,\mid\,(m,1)\in R_i\,\right\}$ for $i=1,2$ . Therefore,

\begin{eqnarray*} \widehat{\,L_1}\cdot \widehat{\,L_2} &=& [R_1][R_2] = [R_1R_2]\\ &=& [\left\{\,(m_1m_2,1)\,\mid\,(m_1,1)\in R_1, (m_2,1)\in R_2\,\right\}]\\ &=& [\left\{\,(m_1m_2,1)\,\mid\,m_1\in L_1, m_2\in L_2\,\right\}]\\ &=& \sum\left\{\,m\otimes 1\,\mid\,m\in L_1L_2\,\right\}\\ &=& \widehat{\,L_1L_2},\end{eqnarray*}

as summands $m_1m_2\otimes 0 = 0$ in $[R_1R_2]$ can be ignored.

We still have to show that $\widehat{\,\cdot\,}$ is surjective. We use $\sum$ and $\otimes$ for the given operations of $K\mathop{\otimes_{\mathcal{R}}} C_2'$ , $\sum'$ and $\otimes'$ for those of ${\mathcal{R}} K\mathop{\otimes_{\mathcal{R}}} C_2'$ . By the universal property of ${\mathcal{R}} K\mathop{\otimes_{\mathcal{R}}} C_2'$ , the given $\sum : {\mathcal{R}} K \to K$ induces an ${\mathcal{R}}$ -morphism $h=h_{f,g}$ for $f=\top_1\circ \sum$ and $g=\top_2$ such that $f=h\circ \top_1'$ and $g=h\circ\top_2'$ :

Since h is a homomorphism and $h(\top_2'(c)) = \top_1(c)$ for $c\in C_2'$ , h preserves commutativity relations with $C_2'$ , so its restriction is an ${\mathcal{R}}$ -morphism

\begin{equation*} h:Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})\to Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}).\end{equation*}

Clearly, $h:{\mathcal{R}} K\mathop{\otimes_{\mathcal{R}}} C_2'\to K\mathop{\otimes_{\mathcal{R}}} C_2'$ is surjective: if $R\in{\mathcal{R}}(K\times C_2')$ we have

\begin{eqnarray*} [R] &=& \sum\left\{\,m\otimes c\,\mid\,(m,c)\in R\,\right\} \\ &=& \sum\left\{\,\left(\sum\{m\}\right)\otimes c\,\mid\,(m,c)\in R\,\right\} \\ &=& h\left({\textstyle{\displaystyle\sum}'}\left\{\,\{m\}\otimes' c\,\mid\,(m,c)\in R\,\right\}\right)\\\ &=& h([R'])\end{eqnarray*}

for $ R'=\left\{\,(\{m\},c)\,\mid\,(m,c)\in R\,\right\} \in {\mathcal{R}}({\mathcal{R}} K\times C_2'). $ And if $[R]\in Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ , then $[R']\in Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ , so the restriction $h:Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})\to Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ also is surjective.

Now take $[R]\in Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ with $R\in{\mathcal{R}}(K\times C_2')$ , and let $R'=\left\{\,(\{m\},c)\,\mid\,(m,c)\in R\,\right\}$ . By Theorem 27, for $[R']\in Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ there is $L\in{\mathcal{C}} K$ such that

\begin{equation*} [R'] = {\textstyle{\displaystyle\sum}'}\widetilde{\top_1'}(L) = {\textstyle{\displaystyle\sum}'}\left\{\,\{m\}\otimes' 1\,\mid\,m\in L\,\right\} . \end{equation*}

We claim that $[R] = \widehat L = \sum\left\{\,m\otimes 1\,\mid\,m\in L\,\right\}$ . By Lemma 29, there is $S\in {\mathcal{R}}(K\times C_2')$ with $S\subseteq K\times \{0,1\}$ and $L = \left\{\,m\,\mid\,(m,1)\in S\,\right\}$ . Then $S'=\left\{\,(\{m\},c)\,\mid\,(m,c)\in S\,\right\}\in{\mathcal{R}}({\mathcal{R}} K\times C_2')$ and

\begin{equation*} [S'] = {\textstyle{\displaystyle\sum}'}\left\{\,\{m\}\otimes' 1\,\mid\,m\in L\,\right\} = [R']; \end{equation*}

hence, $[R]=h([R'])=h([S'])=[S] = \sum\left\{\,m\otimes c\,\mid\,(m,c)\in S\,\right\} =\sum\widetilde{\top_1}(L) = \widehat L$ .

In contrast to Theorem 17, the map $\widehat{\,\cdot\,}: {\mathcal{C}} K\to Z_{C_2}({K} \mathop{\otimes_{\mathcal{R}}} {C_2})$ need not be injective:

Example 7. Take $K={\mathcal{R}} M$ for $M= \{a,b\}^*$ . For $L\in K$ , $\left\{\,\{m\}\,\mid\,m\in L\,\right\}\in{\mathcal{R}}({\mathcal{R}}M)$ , and since $L\mapsto L\otimes 1$ is the ${\mathcal{R}}$ -morphism $\top_1: K \to K\mathop{\otimes_{\mathcal{R}}} C_2'$ , we have

\begin{equation*}L\otimes 1 = \left(\bigcup\left\{\,\{m\}\,\mid\,m\in L\,\right\}\right) \otimes 1 =\sum\left\{\,\{m\}\otimes 1\,\mid\,m\in L\,\right\}.\end{equation*}

It follows that for $U\in {\mathcal{C}} K$ ,

\begin{equation*} \widehat U = \sum\left\{\,L\otimes 1\,\mid\,L\in U\,\right\} = \sum\left\{\,\{m\}\otimes 1\,\mid\,m\in \bigcup U\,\right\}.\end{equation*}

Consider the following two polynomial systems over K:

\begin{eqnarray*} x &\geq& \{ \{1,ab\}\} \cup x \cup \{\{a\}\}x\{\{b\}\} \cup \{\{a^2\}\}x\{\{b^2\}\}, \\ x &\geq& \{ \{1,a^2b^2\}, \{ab,a^3b^3\}\} \cup x \cup \{\{a^2\}\}x\{\{b^2\}\} \end{eqnarray*}

The least solutions $U_1, U_2\in {\mathcal{C}} K$ of these are, respectively,

\begin{equation*} U_1 = \left\{\,\{a^nb^n,a^{n+1}b^{n+1}\}\,\mid\,n\in{\mathbb{N}}\,\right\} \quad\textrm{and}\quad U_2 = \left\{\,\{a^nb^n,a^{n+2}b^{n+2}\}\,\mid\,n\in{\mathbb{N}}\,\right\}. \end{equation*}

But while $U_1\not=U_2$ , we have $\bigcup U_1 = \bigcup U_2=\left\{\,a^nb^n\,\mid\,n\in{\mathbb{N}}\,\right\}$ ; hence, $\widehat{U_1}=\widehat{U_2}$ . $\diamond$

Lemma 31. For each ${\mathcal{R}}$ -dioid K, $Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is a ${\mathcal{C}}$ -dioid. Moreover,

\begin{equation*} Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}) = \left\{\,[R]\,\mid\,R\in {\mathcal{R}}(K\times C_2'), R\subseteq K\times \{0,1\}\,\right\}. \end{equation*}

Proof. By Lemma 30, the map $\widehat{\,\cdot\,}:{\mathcal{C}} K\to Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is a surjective homomorphism that assigns to $L\in{\mathcal{C}} K$ the least upper bound of the image of L under the homomorphism $\top_1:K\to K\mathop{\otimes_{\mathcal{R}}} C_2'$ , $\widehat{\,L\,}=\sum\widetilde{\top_1}(L)$ . By Lemma 3, $Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is a ${\mathcal{C}}$ -dioid, i.e. there is a ${\mathcal{C}}$ -distributive least upper bound operator

\begin{equation*}\sum:{\mathcal{C}}(Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}))\to Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}),\end{equation*}

where for $V\in {\mathcal{C}}(Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}))$ , $\sum V = \widehat{\bigcup U}$ for any $U\in {\mathcal{C}}{\mathcal{C}} K$ such that $V = \left\{\,\widehat L\,\mid\,L\in U\,\right\}$ .

For $\supseteq$ of the equation, suppose $R\in {\mathcal{R}}(K\times C_2')$ and $R\subseteq K\times\{0,1\}$ . By $\supseteq$ of Lemma 29,

\begin{equation*} L := \left\{\,m\,\mid\,(m,1)\in R\,\right\} \in {\mathcal{C}} K. \end{equation*}

But then $[R] = \widehat{L} \in Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ by Lemma 30. The reverse inclusion $\subseteq$ follows from the surjectivity of $\widehat{\,\cdot\,}$ and $\subseteq$ of Lemma 29, as shown at the beginning of the proof of Lemma 30.

Before we can present the second main result, that for any ${\mathcal{R}}$ -dioid K, $Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is the ${\mathcal{C}}$ -closure of K, we have to consider a special case ⁸ :

Theorem 32. Let C be a ${\mathcal{C}}$ -dioid and K its restriction to an ${\mathcal{R}}$ -dioid. The ${\mathcal{R}}$ -morphism $\top_1: K\to K\mathop{\otimes_{\mathcal{R}}} C_2'$ is a ${\mathcal{C}}$ -isomorphism

\begin{equation*}C \stackrel{\simeq}{\longrightarrow} Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}).\end{equation*}

Proof. By Lemma 31, $D:=Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is a ${\mathcal{C}}$ -dioid, so let $\sum:{\mathcal{C}}D\to D$ be its supremum operator. Since C and K have the same multiplicative monoid, ${\mathcal{C}} C = {\mathcal{C}} K$ , so let ${\textstyle{\sum'}}:{\mathcal{C}} K\to K$ be the supremum operator of the ${\mathcal{C}}$ -dioid C. We show that the ${\mathcal{R}}$ -morphism $\top_1$ of the tensor product

\begin{equation*}{\top_1} : {K} \longrightarrow {K\mathop{\otimes_{\mathcal{R}}} C_2'} \longleftarrow {C_2'} : {\top_2},\end{equation*}

is a surjective ${\mathcal{C}}$ -morphism $\top_1:C \to D$ , and its inverse $m\otimes 1 \mapsto m$ is a ${\mathcal{C}}$ -morphism $j:D\to C$ .

With $\eta:K\to {\mathcal{C}} K$ , $\eta(m)=\{m\}$ for $m\in K$ , we have

\begin{equation*} \top_1(m) = m\otimes 1 = \sum\{m\otimes 1\} = \sum\widetilde{\top_1}(\{m\}) = \left(\sum\circ\widetilde{\top_1}\circ\eta\right)(m), \end{equation*}

and consider the following diagram:

To show that $\top_1:K\to D$ is a ${\mathcal{C}}$ -morphism, we must show that for every $L\in{\mathcal{C}} K$ ,

(13) \begin{equation} \left({\textstyle{\displaystyle\sum}'} L\right)\otimes 1 =\sum\left\{\,m\otimes 1\,\mid\,m\in L\,\right\}. \end{equation}

Clearly, $(\sum'L)\otimes 1$ is an upper bound of $\left\{\,m\otimes 1\,\mid\,m\in L\,\right\} = \widetilde{\top_1}(L)$ , so

\begin{equation*} \widehat L := \sum\left\{\,m\otimes 1\,\mid\,m\in L\,\right\} \leq ({\textstyle{\displaystyle\sum}'} L)\otimes 1.\end{equation*}

For the reverse inequation $\widehat L \geq (\sum'L)\otimes 1$ , recall that $C_2' = {\mathcal{R}}\Delta_2^*/\rho_2$ embeds into the polycyclic ${\mathcal{C}}$ -dioid $C_{2,{\mathcal{C}}}' = {\mathcal{C}}\Delta_2^*/\rho_2$ of Section 2.2. Consider the tensor product

\begin{equation*} {\top_1'} : {C} \longrightarrow {C\mathop{\otimes_{\mathcal{C}}} C_{2,{\mathcal{C}}}'} \longleftarrow {C_{2,{\mathcal{C}}}'} : {\top_2'} \end{equation*}

in the category of ${\mathcal{C}}$ -dioids. Since $\top_1'$ is a ${\mathcal{C}}$ -morphism,

\begin{equation*} \left({\textstyle{\displaystyle\sum}'} L\right)\otimes'1' = \top_1'\left({\textstyle{\displaystyle\sum}'} L\right) = {\textstyle{\displaystyle\sum}'}\widetilde{\top_1'}(L) = {\textstyle{\displaystyle\sum}'}\left\{\,m\otimes' 1'\,\mid\,m\in L\,\right\},\end{equation*}

where we write 1’ for the unit in $C_{2,{\mathcal{C}}}'$ , $\top_1'(c)= c\otimes'1'$ for $c\in C$ , and on the right, $\sum'$ also for the supremum operator of $C\mathop{\otimes_{\mathcal{C}}} C_{2,{\mathcal{C}}}'$ . Combined with the identity from K to C, the embedding of $C_2'$ into $C_{2,{\mathcal{C}}}'$ gives a monotone embedding ${\mathcal{R}}$ -morphism $h:K\mathop{\otimes_{\mathcal{R}}} C_2' \to C\mathop{\otimes_{\mathcal{C}}}C_{2,{\mathcal{C}}}'$ . Therefore,

\begin{eqnarray*} h\left(\left({\textstyle{\sum'}} L\right)\otimes 1\right) &=& \left({\textstyle{\sum'}} L\right)\otimes' 1'\\ &=& {\textstyle{\displaystyle\sum}'}\left\{\,m\otimes' 1'\,\mid\,m\in L\,\right\}\\ &=& {\textstyle{\displaystyle\sum}'}\left\{\,h(m\otimes 1)\,\mid\,m\in L\,\right\}\\ &=& {\textstyle{\displaystyle\sum}'}\,\widetilde{h}(\widetilde{\top_1}(L))\\ &\leq& h(\widehat L),\end{eqnarray*}

where the inequation holds since $\widehat L$ is an upper bound of $\widetilde{\top_1}(L)$ . Together with $\widehat L\leq (\sum' L)\otimes 1$ , this gives $h((\sum' L)\otimes 1) = h(\widehat L)$ , and as h is injective, (13). So $\top_1:K \to D$ is a ${\mathcal{C}}$ -morphism.

It follows that $\widehat{\,\cdot\,} = \top_1\circ \sum' : {\mathcal{C}} K \to D$ is a ${\mathcal{C}}$ -morphism, because ${\textstyle{\sum'}}:{\mathcal{C}} C\to C$ and $\top_1:C\to D$ are ${\mathcal{C}}$ -morphisms. Since $\widehat{\,\cdot\,}:{\mathcal{C}} K\to D$ is surjective, so is $\top_1:K\to D$ , by (13); hence,

\begin{equation*} D = \left\{\,m\otimes 1\,\mid\,m\in K\,\right\}. \end{equation*}

It remains to be shown that its inverse $j:D\to K$ , $m\otimes 1\mapsto m$ , is a ${\mathcal{C}}$ -morphism. The surjective homomorphism $\widehat{\,\cdot\,}:{\mathcal{C}} K\to D$ lifts to a surjective homomorphism from ${\mathcal{C}}{\mathcal{C}} K$ to ${\mathcal{C}} D$ . Hence for $V\in {\mathcal{C}} D,$ there is $U\in {\mathcal{C}}{\mathcal{C}} K$ with $V=\left\{\,\widehat L\,\mid\,L\in U\,\right\}$ , and since $\bigcup U \in {\mathcal{C}} K$ and $\widehat{\,\cdot\,}$ is a ${\mathcal{C}}$ -morphism,

\begin{equation*} \sum V = \sum\left\{\,\widehat L\,\mid\,L\in U\,\right\} = \widehat{\bigcup U} =({\textstyle{\displaystyle\sum}'} \bigcup U)\otimes 1\end{equation*}

by (13). By applying j and using (13) for each $L\in U$ ,

\begin{eqnarray*} j\left(\sum V\right) &=& {\textstyle{\displaystyle\sum}'}\bigcup U\\ &=&{\textstyle{\displaystyle\sum}'}\left\{\,{\textstyle{\displaystyle\sum}'} L\,\mid\,L\in U\,\right\}\\ &=& {\textstyle{\displaystyle\sum}'}\left\{\,j(({\textstyle{\displaystyle\sum}'} L)\otimes 1)\,\mid\,L\in U\,\right\}\\ &=& {\textstyle{\displaystyle\sum}'}\left\{\,j(\widehat L)\,\mid\,L\in U\,\right\}\\ &=& {\textstyle{\displaystyle\sum}'}\left\{\,j(v)\,\mid\,v\in V\,\right\}.\end{eqnarray*}

Therefore, $j:D\to K$ is ${\mathcal{C}}$ -continuous, i.e. preserves suprema of ${\mathcal{C}}$ -sets.

Under the assumptions of Theorem 32, $\left\{\,(L,\{{\textstyle{\displaystyle\sum}'} L\})\,\mid\,L\in{\mathcal{C}} K\,\right\}\subseteq \ker(\widehat{\,\cdot\,})$ , because by (13)

\begin{equation*} \widehat L = ({\textstyle{\displaystyle\sum}'} L)\otimes 1 = \sum\left\{\,m\otimes 1\,\mid\,m\in\{{\textstyle{\sum'}} L\}\,\right\} = \widehat{\{\textstyle{\sum'L}\}}.\end{equation*}

We can now prove our second main result, which will imply that ${\mathcal{C}}K/\ker(\widehat{\,\cdot\,}) \simeq {Q_{\mathcal{R}}^{\mathcal{C}}}(K)$ :

Theorem 33 (Algebraic representation of ${\mathcal{C}}$ -closure) For any ${\mathcal{R}}$ -dioid K, there is a ${\mathcal{C}}$ -isomorphism

\begin{equation*} {Q_{\mathcal{R}}^{\mathcal{C}}}(K) \simeq Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'}). \end{equation*}

Proof. It is sufficient to prove that $D:=Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is a ${\mathcal{C}}$ -completion of K. Let $\eta:K\to D$ be the embedding obtained from $\top_1 :K\to K\mathop{\otimes_{\mathcal{R}}}{C_2'}$ ,

\begin{equation*} \eta(m) := \top_1(m) = m\otimes 1 \in D \quad \textrm{ for }m\in K,\end{equation*}

and $f:K\to C$ an ${\mathcal{R}}$ -morphism to a ${\mathcal{C}}$ -dioid C. Define $\bar f : D\to C$ by

\begin{equation*} \bar f(\widehat L) := \sum\left\{\,f(m)\,\mid\,m\in L\,\right\} = \sum\widetilde f(L) \quad\textrm{ for }L\in{\mathcal{C}} K.\end{equation*}

We prove later that $\bar f$ is well-defined and first show the remaining properties.

$f = \bar f \circ \eta$ : for $m\in K$ , $\bar f(\eta(m)) = \bar f(\sum\{m\otimes 1\}) = \bar f(\widehat{\{m\}}) = \sum\{f(m)\} = f(m)$ .

$\bar f$ is a monotone homomorphism: $\bar f(1) = \bar f(\widehat{\{1\}}) =\sum\{f(1)\} = f(1) = 1$ , and since $\widehat{\,\cdot\,}:{\mathcal{C}} K\to D$ is a homomorphism and $\sum\circ \widetilde f:{\mathcal{C}} K\to C$ is ${\mathcal{C}}$ -distributive,

\begin{equation*} \bar f(\widehat L\cdot \widehat{L'}) =\bar f(\widehat{L L'}) = \sum\widetilde f(LL')= \sum\widetilde f(L)\sum \widetilde f(L') = \bar f(\widehat L)\bar f(\widehat{L'}).\end{equation*}

$\bar f$ is ${\mathcal{C}}$ -continuous: Suppose $V\in{\mathcal{C}} D$ . Since $\widehat{\,\cdot\,}:{\mathcal{C}} K\to D$ is a surjective homomorphism, so is its lifting to ${\mathcal{C}}{\mathcal{C}} K\to {\mathcal{C}} D;$ hence, there is $U\in {\mathcal{C}}{\mathcal{C}} K$ such that $V= \left\{\,\widehat L\,\mid\,L\in U\,\right\}\in {\mathcal{C}} D$ . Therefore,

\begin{eqnarray*} \bar f\left(\sum V\right) &=& \bar f\left(\sum\left\{\,m\otimes 1\,\mid\,m\in \bigcup U\,\right\}\right)\\ &=& \bar f\left(\widehat{\bigcup U}\right)\\ &=& \sum\widetilde f\left(\bigcup U\right)\\ &=& \sum\bigcup\left\{\,\widetilde f(L)\,\mid\,L\in U\,\right\}\\ &=& \sum\left\{\,\bar f(\widehat L)\,\mid\,L\in U\,\right\}.\\ &=& \sum\left\{\,\bar f(v)\,\mid\,v\in V\,\right\}.\end{eqnarray*}

$\bar f$ is well-defined: Suppose $L,L'\in{\mathcal{C}} K$ and $\widehat{L}=\widehat{L'}$ . We must show

(14) \begin{equation} \sum{\widetilde f(L)} = \sum{\widetilde f(L')}.\end{equation}

Let $K' = {Q_{\mathcal{C}}^{\mathcal{R}}}(C)$ be the restriction of C to an ${\mathcal{R}}$ -dioid,

\begin{equation*} {\top_1'} : {K'} \longrightarrow {K'\mathop{\otimes_{\mathcal{R}}} C_2'} \longleftarrow {C_2'} : {\top_2'} \end{equation*}

its tensor product with $C_2'$ in ${\mathbb{D}}{\mathcal{R}}$ , and $D' := Z_{C_2'}({K'} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ . By Theorem 32, $\top_1' : C \to D'$ is a ${\mathcal{C}}$ -isomorphism, with inverse $j:D'\to C$ . We write $\top_1'(c) =c\otimes' 1$ for $c\in K'$ and $\sum'$ for the least upper bound operator of D’ or $K'\mathop{\otimes_{\mathcal{R}}} C_2'$ .

Consider the commuting ${\mathcal{R}}$ -morphisms $f'=\top_1'\circ f$ and $g'=\top_2'$ shown in

Let $h_{f',g'}$ be the ${\mathcal{R}}$ -morphism with $f'=h_{f',g'}\circ \top_1$ and $g'=h_{f',g'}\circ \top_2$ . For $R\in{\mathcal{R}}(K\times C_2')$ , put $R_f = \left\{\,(f(m),c)\,\mid\,(m,c)\in R\,\right\}\in{\mathcal{R}}(K'\times C_2')$ . Then,

\begin{eqnarray*} h_{f',g'}([R]) &=& h_{f',g'}\left(\sum\left\{\,m\otimes c\,\mid\,(m,c)\in R\,\right\}\right)\\ &=& \sum\left\{\,f'(m)g'(c)\,\mid\,(m,c)\in R\,\right\}\\ &=& \sum\left\{\,(f(m)\otimes 1)(1'\otimes c)\,\mid\,(m,c)\in R\,\right\}\\ &=& \sum\left\{\,f(m)\otimes c\,\mid\,(m,c)\in R\,\right\}\\ &=& [R_f].\end{eqnarray*}

The restriction of $h_{f',g'}$ to $D\subseteq K\mathop{\otimes_{\mathcal{R}}} C_2'$ clearly is an ${\mathcal{R}}$ -morphism $h':D\to D'$ . The situation is visualized by the following diagram:

By Lemma 29, there are $R,R'\in {\mathcal{R}}(K\times C_2')$ with $R,R'\subseteq K\times\{0,1\}$ and $L=\left\{\,m\,\mid\,(m,1)\in R\,\right\}$ , $L'=\left\{\,m\,\mid\,(m,1)\in R'\,\right\}$ , so

\begin{equation*} [R] = \widehat L = \widehat{L'} = [R']. \end{equation*}

By an application of $h_{f',g'}$ , $[R_f]=[R_f']$ . Using $\widetilde f(L)\in {\mathcal{C}} K'$ , we get

\begin{equation*} \begin{array}{rcl@{\qquad}l} [R_f] &=& \widehat{\widetilde f(L)}'\\ &=& {\textstyle{\displaystyle\sum}'}\left\{\,f(m)\otimes' c\,\mid\,(m,c)\in R\,\right\} &\\ &=& {\textstyle{\displaystyle\sum}'}\left\{\,f(m)\otimes' 1\,\mid\,(m,1)\in R\,\right\} & (R\subseteq K\times \{0,1\})\\ &=&{\textstyle{\displaystyle\sum}'}\left\{\,f(m)\otimes' 1\,\mid\,m\in L\,\right\} & (L = \left\{\,m\,\mid\,(m,1)\in R\,\right\})\\ &=& \left({\textstyle{\displaystyle\sum}'}{\widetilde f}(L)\right)\otimes' 1 & (\textrm{by (13) on {D}'}).\end{array}\end{equation*}

Likewise, $[R_f'] = \widehat{\widetilde f(L')}'= (\sum\widetilde f (L')) \otimes' 1$ , and so

\begin{equation*} \left(\sum\widetilde f(L)\right) \otimes' 1 = [R_f] = [R_f'] = \left(\sum\widetilde f(L')\right) \otimes' 1.\end{equation*}

(Hence, $h'\circ \widehat{\,\cdot\,}\, =\, \widehat{\,\cdot\,}'\circ\widetilde f$ is a ${\mathcal{C}}$ -morphism.) An application of j gives (14).

$\bar f$ is the unique ${\mathcal{C}}$ -morphism $h:D\to C$ with $f = h\circ \eta$ : Suppose h is such a ${\mathcal{C}}$ -morphism and e an element of D. By Lemma 30 there is $L\in{\mathcal{C}} K$ such that $e=\widehat L =\sum\!\left\{\,\!m\otimes 1\,\mid\,m\in L\!\,\right\}$ ; hence,

\begin{eqnarray*} h(e) &=& h(\widehat L)\\ &=& h\left(\sum\left\{\,m\otimes 1\,\mid\,m\in L\,\right\}\right)\\ &=& \sum\left\{\,h(m\otimes 1)\,\mid\,m\in L\,\right\}\\ &=& \sum\left\{\,h(\eta(m))\,\mid\,m\in L\,\right\}\\ &=& \sum\left\{\,f(m)\,\mid\,m\in L\,\right\}\\ &=& \bar f(\widehat{L}) = \bar f(e).\end{eqnarray*}

Therefore, $h=\bar f$ .

Corollary 34. For any ${\mathcal{R}}$ -dioid K, the ${\mathcal{C}}$ -closure of K is ${\mathcal{C}} K/\ker({\widehat{\,\cdot\,}})$ .

Proof. By Theorem 33, $D := Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is the ${\mathcal{C}}$ -closure of K, so we must show that ${\mathcal{C}} K/\ker(\widehat{\,\cdot\,})$ is a ${\mathcal{C}}$ -dioid and there is a ${\mathcal{C}}$ -isomorphism between D and ${\mathcal{C}}K/\ker(\widehat{\,\cdot\,})$ . By Lemma 30, $\widehat{\,\cdot\,}:{\mathcal{C}} K\to D$ is a monotone and surjective homomorphism between ${\mathcal{C}}$ -dioids. It is a ${\mathcal{C}}$ -morphism, because $\widehat{\bigcup U} = \sum\left\{\,\widehat L\,\mid\,L\in U\,\right\}$ for $U\in{\mathcal{C}}{\mathcal{C}} K$ . Hence, its kernel $\ker(\widehat{\,\cdot\,})$ is a ${\mathcal{C}}$ -congruence on ${\mathcal{C}} K$ , and so ${\mathcal{C}} K/\ker(\widehat{\,\cdot\,})$ is a ${\mathcal{C}}$ -dioid. Let us verify that the bijection between ${\mathcal{C}}K/\ker(\widehat{\,\cdot\,})$ and D is a ${\mathcal{C}}$ -isomorphism. In the one direction, the mapping $f:{\mathcal{C}} K/\ker(\widehat{\,\cdot\,})\to D$ , well-defined by $f(L/\ker(\widehat{\,\cdot\,})) = \widehat{L}$ for $L\in{\mathcal{C}} K$ , is a ${\mathcal{C}}$ -morphism, since for $V\in{\mathcal{C}}({\mathcal{C}} K/\ker(\widehat{\,\cdot\,}))$ there is $U\in {\mathcal{C}} {\mathcal{C}} K$ such that $V= \left\{\,L/\ker(\widehat{\,\cdot\,})\,\mid\,L\in U\,\right\}$ , and by the definition of $\sum$ on quotients, $\sum V= (\bigcup U)/\ker(\widehat{\,\cdot\,})$ , so $f(\sum V) = \widehat{\bigcup U} =\sum\left\{\,\widehat L\,\mid\,L\in U\,\right\}=\sum\widetilde f(V)$ . In the other direction, by Lemmas 31 and 29, elements of D are congruence classes [R] of sets $R\in{\mathcal{R}}(K\times C_2')$ with $R\subseteq K\times\{0,1\}$ , such that $[R]=\widehat{L_R}$ for $L_R :=\left\{\,m\,\mid\,(m,1)\in R\,\right\} \in {\mathcal{C}} K$ . Hence, a map $g:D\to {\mathcal{C}}K/\ker(\widehat{\,\cdot\,})$ is well-defined by

\begin{equation*} g([R]) = L_R/\ker(\widehat{\,\cdot\,}), \quad\textrm{ for $R\in {\mathcal{R}}(K\times C_2')$ with $R\subseteq K\times\{0,1\}$},\end{equation*}

and obviously g and f are inverses of each other. To see that g is a ${\mathcal{C}}$ -morphism, suppose $V\in {\mathcal{C}} D$ . There is $U\in{\mathcal{C}}{\mathcal{C}} K$ such that $V= \left\{\,\widehat L\,\mid\,L\in U\,\right\}$ , and $\sum V = \widehat{\bigcup U}$ . There is $R\in{\mathcal{R}}(K\times C_2')$ with $R\subseteq K\times\{0,1\}$ and $\widehat{\bigcup U} = [R]=\widehat{L_R}$ , and so

\begin{equation*} g\left(\sum V\right) = L_R/\ker(\widehat{\,\cdot\,})=\left(\bigcup U\right)/\ker(\widehat{\,\cdot\,}) = \sum\left\{\,L/\ker(\widehat{\,\cdot\,})\,\mid\,L\in U\,\right\} = \sum\widetilde g(V),\end{equation*}

using suitable $R_L\in {\mathcal{R}}(K\times C_2')$ with $R_L\subseteq K\times\{0,1\}$ and $\widehat L = [R_L]$ for the last step.

7. Conclusion

The algebraic abstraction of the regular subsets ${\mathcal{R}} M$ and the context-free subsets ${\mathcal{C}} M$ of a monoid M are the categories of ${\mathcal{R}}$ -dioids or ${}^*$ -continuous Kleene algebras and ${\mathcal{C}}$ -dioids or $\mu$ -continuous Chomsky algebras. Just as ${\mathcal{C}} M$ is the closure of ${\mathcal{R}}M$ under a well-behaved least fixed-point operator $\mu$ , each ${\mathcal{R}}$ -dioid K has a closure $\overline K$ as ${\mathcal{C}}$ -dioid, briefly called its fixed-point closure. We have shown that $\overline K$ can be represented in the product $K\mathop{\otimes_{\mathcal{R}}} C_2'$ of K with $C_2'$ in the category of ${\mathcal{R}}$ -dioids, where the polycyclic ${\mathcal{R}}$ -dioid $C_2'$ on two generators is a quotient of the regular sets ${\mathcal{R}} \Delta_2^*$ over an alphabet $\Delta_2=\{b,d,p,q\}$ of two pairs of brackets, b,d and p,q. Namely, $\overline K$ is isomorphic to the centralizer $Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ of $C_2'$ in $K\mathop{\otimes_{\mathcal{R}}} C_2'$ , which, intuitively, consists of the sums over regular sets of elements $m\otimes c$ where $m\in K$ and $c\in C_2'$ is restricted to be 0 or 1.

This representation theorem is an algebraic form and categorical generalization of the classical Chomsky–Schützenberger theorem (and its reverse) of formal language theory. The latter reduces the set ${\mathcal{C}} X^*$ of context-free languages over a finite alphabet X to the set ${\mathcal{R}}(X\cup\Delta_2)^*$ of regular languages over $X\cup\Delta_2$ , by means of intersection with the context-free Dyck language $D_2(X)\in{\mathcal{C}}(X\cup\Delta_2)^*$ of balanced bracketed strings and the bracket-erasing homomorphism from $(X\cup\Delta_2)^*$ to $X^*$ . In the special case $K={\mathcal{R}} X^*$ with $\overline K={\mathcal{C}} X^*$ , the representation theorem intuitively splits bracketed strings $u\in(X\cup\Delta_2)^*$ to pairs $(w,t)\in X^*\times \Delta_2^*$ and performs the balance-checking and bracket-erasure within $C_2'$ by algebraically reducing the second component of $\{w\}\otimes \{t\} \in K\mathop{\otimes_{\mathcal{R}}} C_2'$ to 1 or 0, depending on whether t belongs to the pure Dyck language $D_2\in{\mathcal{C}}\Delta_2^*$ or not. The underlying part of deriving from $L\in {\mathcal{C}} X^*$ a suitable regular set R of strings $u\in (X\cup\Delta_2)^*$ is as in the classical Chomsky–Schützenberger theorem (cf. Theorem 15). A finite automaton for $R\subseteq (X\cup\Delta_2)^*$ represents L in the sense that the words $u\in R$ evaluate in ${\mathcal{R}} X^*\mathop{\otimes_{\mathcal{R}}} C_2'$ to 0 or to the elements $\{w\}\otimes 1$ with $w=h_{X^*}(u)\in L$ (cf. Figure 2).

The algebra ${\mathcal{R}} X^*\mathop{\otimes_{\mathcal{R}}} C_2'$ is hoped to turn out useful to construct CFG-parsers for context-free languages over X, for example by simplifying the calculation of item-sets of LR-parsers.

Some remarks on the difference between using the bra-ket ${\mathcal{R}}$ -dioid $C_2$ and the polycyclic ${\mathcal{R}}$ -dioid $C_2'$ are in order. Theorem 5 of Hopkins and Leiß (2018) announced that ${\mathcal{C}} M \simeq Z_{C_2}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2})$ for monoids M, indicating that “the equation $db+qp=1$ not present in $C_2'$ is needed to encode stack operations in $C_2.$ ” We here have shown that one can actually do without this equation and prove the stronger result ${\mathcal{C}} M\simeq Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ . One may obtain $C_2$ as the quotient $C_2'/{\left\langle {db+qp=1}\right\rangle}$ of $C_2'$ by the ${\mathcal{R}}$ -congruence generated by the completeness equation. The quotient map is not injective, but its extension to ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ apparently does not identify different members of $Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ , so the announced claim with $C_2$ should follow.

The motivation for writing this article came from an effort to understand Hopkins’ unpublished proof that the fixed-point closure $\overline K$ of an ${\mathcal{R}}$ -dioid K can be algebraically represented by $Z_{C_2}({K} \mathop{\otimes_{\mathcal{R}}} {C_2})$ . An inspection of the proof showed that the completeness assumption $db+qp=1$ of $C_2$ was not used for the analog $\overline K \subseteq Z_{C_2}({K} \mathop{\otimes_{\mathcal{R}}} {C_2})$ of the Chomsky–Schützenberger theorem. For the reverse $Z_{C_2}({K} \mathop{\otimes_{\mathcal{R}}} {C_2})\subseteq \overline K$ , the assumption is used to show that $\widehat{\,\cdot\,}:{\mathcal{C}} K\to Z_{C_2}({K} \mathop{\otimes_{\mathcal{R}}} {C_2})$ given by $\widehat L = \sum\left\{\,m\otimes 1\,\mid\,m\in L\,\right\}$ is surjective. The surjectivity follows from an interesting automata-theoretic Normal Form Theorem for elements of $K\mathop{\otimes_{\mathcal{R}}} C_2$ , which implicitly assumes that ${\textit Mat}_{n,n}({K\mathop{\otimes_{\mathcal{R}}} C_2})$ is an ${\mathcal{R}}$ -dioid and shortly is as follows. For each element $e=[R]\in K\mathop{\otimes_{\mathcal{R}}} C_2$ , by induction on the construction of $R\in {\mathcal{R}}(K\times C_2),$ there is an automaton ${\left\langle {S,A,F}\right\rangle}$ such that e is the language accepted by the automaton, i.e. $e=SA^*F =\sum\left\{\,SA^kF\,\mid\,k\in{\mathbb{N}}\,\right\}$ , where for some n, $S\in \{0,1\}^{1\times n}$ and $F\in \{0,1\}^{n\times 1}$ code the sets of initial and final states and A is a transition matrix $U + X + V \in {\textit Mat}_{n,n}({K\mathop{\otimes_{\mathcal{R}}} C_2})$ with $X\in K^{n\times n}$ , $U\in \{b,p,0\}^{n\times n}$ , $V\in\{d,q,0\}^{n\times n}$ . It is then shown that $N = b(Up+X+qV)d$ is a least solution of $y\geq (UyV+X)^*$ in ${\textit Mat}_{n,n}({K\mathop{\otimes_{\mathcal{R}}} C_2})$ , a version of Dyck’s language, and $N\in (Z_{C_2}({K} \mathop{\otimes_{\mathcal{R}}} {C_2}))^{n\times n}$ . Using the completeness assumption $db+qp=1$ , Hopkins proves

\begin{equation*} e = S(NV)^*N(UV)^*F, \end{equation*}

which simplifies to $e=SNF$ for $e\in Z_{C_2}({K} \mathop{\otimes_{\mathcal{R}}} {C_2})$ . Notice that the Normal Form Theorem provides us with a description both of elements in the centralizer of $C_2$ and of arbitrary elements of $K\mathop{\otimes_{\mathcal{R}}} C_2$ , while the proof of $\overline K=Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ in Section 6 above only gives us a description of elements of the centralizer of $C_2'$ as equivalence classes [R] of $R\in{\mathcal{R}}(K\times C_2')$ with $R\subseteq K\times\{0,1\}$ . In Section 6, the surjectivity of $\widehat{\,\cdot\,}:{\mathcal{C}} K\to Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is reduced to that of $\widehat{\,\cdot\,}:{\mathcal{C}} K\to Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ , which in turn is shown by giving an inverse. However, it is an interesting question whether the Normal Form Theorem also holds for $K\mathop{\otimes_{\mathcal{R}}} C_2'$ ; Hopkins (personal communication, 2021) has found a partial positive answer. A least solution N of $y\geq(UyV+X)^*$ in ${\textit Mat}_{n,n}({Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})})$ exists, since $Z_{C_2'}({K} \mathop{\otimes_{\mathcal{R}}} {C_2'})$ is a ${\mathcal{C}}$ -dioid, and this category is closed under $n\times n$ -matrix semirings.

Another difference of the proofs is that in the case ${\mathcal{R}} M\mathop{\otimes_{\mathcal{R}}} C_2'$ we can replace the tensor product by a quotient (Corollary 13) and so, strictly speaking, need the tensor product only to represent the ${\mathcal{C}}$ -closure of arbitrary ${\mathcal{R}}$ -dioids K in $K\mathop{\otimes_{\mathcal{R}}} C_2'$ .

A minor question is whether our proof for the special case $K={\mathcal{R}} M$ can be simplified. Since it is well-known that ${\mathcal{C}} X^*$ is related to the polycyclic monoids $P_n'$ , Propositions 20–23 might be implicit in existing literature, such as the one referred to by Render and Kambites (2009). Moreover, it seems inelegant to first show that the maps ${\widehat{\,\cdot\,}} : {{\mathcal{C}} M} \rightleftarrows {Z_{C_2'}(\mathcal{R} \mathop{\otimes_{\mathcal{R}}} {C_2'})} : {{\cdot}^\vee}$ form a bijection and then use this to show that they are ${\mathcal{C}}$ -morphisms.