Algebraic Language Theory with Effects

A finite probability distribution on a set $X$ is a map $d:X\to [0,1]$ whose support $\mathrm{supp}(d):=\{x\in X\mid d(x)\ne 0\}$ is finite and which satisfies ${\sum }_{x\in X}d(x)=1$. A distribution can be represented as a finite formal sum ${\sum }_{i\in I}{r}_i{x}_i$ where $x_i\in X$, $r_i\in [0,1],{\sum }_{i\in I}{r}_i=1$ and $d(x)={\sum }_{i\in I:x_i=x}{r}_i$ for $x\in X$. The set of all distributions on $X$ is denoted by $𝒟X$.

A map of the form $f:X\to 𝒟Y$, denoted by $f:X  ⟶Y$, is a probabilistic channel or Markov kernel from $X$ to $Y$. Intuitively, $f$ is a map from $X$ to $Y$ that assigns to a given input $x$ the output $y$ with probability $f(x)(y)$. We write $X  ⟶Y$ for the set of all probabilistic channels from $X$ to $Y$. Two probabilistic channels $f:X  ⟶Y$ and $g:Y  ⟶Z$ can be composed to yield a probabilistic channel $f⨟g:X  ⟶Z$ given by $(f⨟g)(x)=\left(z\mapsto {\sum }_{y\in Y}f(x)(y)\cdot g(y)(z)\right)$. The unit at $X$ is the probabilistic channel $ηX:X  ⟶X$ sending $x\in X$ to the Dirac distribution ${\delta }_x\in 𝒟X$ defined by ${\delta }_x=(y\mapsto 1\text{ if }x=y\text{ else }0$). Using sum notation, composition of probabilistic channels is given by $(f⨟g)(x)={\sum }_{i\in I}{\sum }_{j\in J_i}{r}_i{r}_{ij}{z}_{ij}$, where $f(x)={\sum }_{i\in I}{r}_i{y}_i$ and $g(y_i)={\sum }_{j\in J_i}{r}_{ij}{z}_{ij}$, and the unit is ${\eta }_X(x)=1x$. Composition $⨟$ of probabilistic channels is associative and has $\eta$ as an identity: $(f⨟g)⨟h=f⨟(g⨟h)$ and ${\eta }_X⨟f=f⨟{\eta }_Y$ for $f:X  ⟶Y,g:Y  ⟶Z$ and $h:Z  ⟶W$. A channel $f:X  ⟶2$ is a probabilistic predicate $f:X\to [0,1]$ on $X$, where we identify $𝒟2$ with the unit interval. A map $f:X\to Y$ induces the pure channel $f;ηY:X  ⟶Y$, which we also denote by $f:X\to Y$ by abuse of notation.

Probabilistic automata, due to Rabin [51], generalize deterministic automata. Transitions are no longer given by a unique successor state $\delta (q,a)$ for every state $q$ and input $a$, but a probability distribution over possible successor states. Accordingly, probabilistic automata compute probabilistic languages, which are simply probabilistic predicates $Σ∗  ⟶2$. Formally:

Comparing with the definition of DFAs in Section 2, we see that DFAs are precisely PFAs where $i$, $\delta$, $o$ are pure maps.

Our aim is to understand PFA-computable probabilistic languages in terms of recognition by algebraic structures, in the same way that finite monoids recognize regular languages. To this end, we introduce two modes of probabilistic algebraic recognition and prove that they capture precisely the PFA-computable languages.

For our first mode of probabilistic algebraic recognition, we stick with finite monoids as recognizing structures, and only add probabilistic effects to the recognizing monoid morphisms. First we need some auxiliary machinery:

Intuitively, ${\xi }_{X,Y}(d)(x)(y)$ is the probability of picking some $f$ according to $d$ satisfying $f(x)=y$. For a channel $g:X  ⟶Y$, the probability of $f:X\to Y$ in the distribution ${\lambda }_{X,Y}(g)$ provides a measure of how compatible $f$ is to $g$. The map ${\pi }_{Y,Z}$ sends two distributions on $Y$ and $Z$ to their product distribution on $Y\times Z$. Well-definedness of $\xi$ and $\lambda$ and the next lemma can be shown by calculation; conceptually, they follow from $𝒟$ being an affine monad.

We stress that, in Definition 3.9, probabilistic effects only appear in the channels $h$ and $p$, while the monoid $M$ itself is pure. At first sight, it may seem more natural to use “probabilistic monoids”, with proper channels as neutral element $1  ⟶M$ and multiplication $M×M  ⟶M$, as recognizers. Remarkably, we need not require this additional generality:

The presence of probabilistic effects in the recognizing morphisms places the above mode of probabilistic recognition outside standard universal algebra. In this section we develop an equivalent, purely algebraic approach based on the theory of convex sets.

A convex set [61] is a set $X$ equipped with a family of binary operations ${+}_r:X\times X\to X$ ($r\in [0,1]$) subject to following equations, where $s^{\prime }=r+s-rs\ne 0$ and $r^{\prime }=\frac{r}{s^{\prime }}$:

A map $f:X\to Y$ between convex sets is affine if $f(x{+}_r{x}^{\prime })=f(x){+}_{r}f(x^{\prime })$ for $x,x^{\prime }\in X$ and $r\in [0,1]$.

Reutenauer [52] showed that finite-dimensional $ℝ$-algebras – real vector spaces equipped with a compatible monoid structure – precisely recognize rational power series ${\mathrm{\Sigma }}^{\ast }\to ℝ$. For algebraic recognition of probabilistic languages, we generalize $ℝ$-algebras to convex monoids, which are monoids with an additional convex structure that is respected by the multiplication:

For a correspondence between PFA-computable languages and convex monoids, we need to impose a suitable finiteness restriction on the latter. Finite convex monoids are not sufficient; instead, we shall work with a more permissive notion of finiteness:

Intuitively, this definition says that $X$ is the convex hull of a finite subset $s[G]\subseteq X$: every element in $X$ is a convex combination of the elements $s(g),g\in G$.

Fg-carried convex monoids give rise to our second algebraic characterization of PFAs:

Compared to ordinary monoids, convex monoids are fairly complex structures. The benefit of the additional complexity is the existence of canonical recognizers for probabilistic languages. Recall that every regular language $L:{\mathrm{\Sigma }}^{\ast }\to 2$ has a canonical recognizer, the syntactic monoid $\mathrm{Syn}(L)$. It is given by the quotient ${\mathrm{\Sigma }}^{\ast }/{\approx }_L$ of the free monoid ${\mathrm{\Sigma }}^{\ast }$ modulo the syntactic congruence ${\approx }_L\subseteq {\mathrm{\Sigma }}^{\ast }\times {\mathrm{\Sigma }}^{\ast }$, where $v{\approx }_{L}w$ iff $L(xvy)=L(xwy)$ for all $x,y\in {\mathrm{\Sigma }}^{\ast }$. The projection $h_L:{\mathrm{\Sigma }}^{\ast }\twoheadrightarrow \mathrm{Syn}(L)$, sending $w\in {\mathrm{\Sigma }}^{\ast }$ to its congruence class $[w]$, recognizes $L$ via $p:\mathrm{Syn}(L)\to 2$ with $p([w])=1\text{ iff }w\in L$. Moreover, $h_L$ factorizes through every surjective morphism $h:{\mathrm{\Sigma }}^{\ast }\twoheadrightarrow M$ recognizing $L$, thus $h_L$ is the “smallest” surjective morphism recognizing $L$. For probabilistic languages, this notion generalizes as follows:

Syntactic structures for formal languages are well-studied from a categorical perspective [14, 63, 2]. The following result is an instance of [2, Thm. 3.14]:

Alternatively, one can construct the syntactic convex monoid as the transition monoid of the minimal $𝒟$-automaton (see the full version [38]), entailing a restriction on the convex structure of syntactic convex monoids:

Syntactic convex monoids are useful as a descriptional tool for characterizing (and potentially deciding) properties of languages in algebraic terms. Here is a simple illustration:

Let us note that while every PFA-computable language is recognized by some fg-carried convex monoid (Theorem 3.18), its syntactic convex monoid is generally not fg-carried:

In the following, familiarity with basic category theory is assumed; see Mac Lane [39] for a gentle introduction. We recall some concepts from the theory of monads [40] to fix our terminology and notation. We write $\mathrm{𝖲𝖾𝗍}$ for the category of sets and functions. A monad $𝕋=(T,\eta ,\mu )$ on $\mathrm{𝖲𝖾𝗍}$ is a triple consisting of an endofunctor $T:\mathrm{𝖲𝖾𝗍}\to \mathrm{𝖲𝖾𝗍}$ and two natural transformations $\eta :\mathrm{𝖨𝖽}\to T$ (the unit) and $\mu :TT\to T$ (the multiplication), satisfying the laws $T\mu \text{;}\mu =\mu T\text{;}\mu$ and $T\eta \text{;}\mu ={\mathrm{𝖨𝖽}}_T=\eta T\text{;}\mu$.

The Kleisli category $𝒦\mathrm{\ell }(𝕋)$ has sets as objects, and a morphism from $X$ to $Y$, denoted $f:X  ⟶Y$, is a map $f:X\to TY$. The composite of $f:X  ⟶Y$ and $g:Y  ⟶Z$ is denoted by $f⨟g:X  ⟶Z$ and defined by $f⨟g=f\text{;}Tg\text{;}{\mu }_Z$. The identity morphism on $X$ is the component $ηX:X  ⟶X$ of the unit. Intuitively, a Kleisli morphism is a function with computational effects given by the monad $𝕋$ [43]. A map $f:X\to Y$ is identified with the Kleisli morphism $f;ηY:X  ⟶Y$; such Kleisli morphisms are said to be pure, since they correspond to effect-free computations. Note that there is no need for operator precedence between $\text{;}$ and $⨟$ since $(f\text{;}g)⨟h=f\text{;}(g⨟h)$ and $(g⨟h)\text{;}k=g⨟(h\text{;}k)$ for all Kleisli morphisms $g:X\to TY,h:Y\to TZ$ and pure maps $f:W\to X,k:TZ\to U$.

Further, a $𝕋$-algebra $(A,a)$ consists of set $A$ (the carrier) and a map $a:TA\to A$ (the structure) satisfying the associative law $Ta\text{;}a={\mu }_A\text{;}a$ and the unit law ${\eta }_A\text{;}a={\mathrm{𝗂𝖽}}_A$. A morphism from $(A,a)$ to a $𝕋$-algebra $(B,b)$ (a $𝕋$-morphism for short) is a map $h:A\to B$ such that $a\text{;}h=Th\text{;}b$. We write $\mathrm{𝖠𝗅𝗀}(𝕋)$ for the category of $𝕋$-algebras and $𝕋$-morphisms. Products in $\mathrm{𝖠𝗅𝗀}(𝕋)$ are formed in $\mathrm{𝖲𝖾𝗍}$: the product algebra of $(A_i,a_i)$, $i\in I$, has the structure $T({\prod }_i{A}_i)\stackrel{{⟨T{p}_i⟩}_i}{\to }{\prod }_{i}T{A}_i\stackrel{{\prod }_i{a}_i}{\to }{\prod }_i{A}_i$, where $p_i:{\prod }_i{A}_i\to A_i$ is the $i$th product projection.

The forgetful functor from $\mathrm{𝖠𝗅𝗀}(𝕋)$ to $\mathrm{𝖲𝖾𝗍}$ has a left adjoint sending a set $X$ to the free $𝕋$-algebra $𝕋X=(TX,{\mu }_X)$ over $X$. For every $𝕋$-algebra $(A,a)$ and every map $h:X\to A$, there exists a unique $𝕋$-morphism $h^{\mathrm{\#}}:𝕋X\to (A,a)$ such that ${\eta }_X\text{;}{h}^{\mathrm{\#}}=h$; that $𝕋$-morphism $h^{\mathrm{\#}}$ is the free extension of $h$. The Kleisli category $𝒦\mathrm{\ell }(𝕋)$ is equivalent to a full subcategory of $\mathrm{𝖠𝗅𝗀}(𝕋)$ via the embedding $X\mapsto 𝕋X$ and $h\mapsto h^{\mathrm{\#}}$.

Monads provide a categorical view of universal algebra. Every finitary algebraic theory $(\mathrm{\Lambda },E)$, given by a signature $\mathrm{\Lambda }$ of finitary operation symbols and a set $E$ of equations between $\mathrm{\Lambda }$-terms, induces a monad $𝕋$ on $\mathrm{𝖲𝖾𝗍}$, where $TX$ is the carrier of the free $(\mathrm{\Lambda },E)$-algebra (viz. the set of all $\mathrm{\Lambda }$-terms over $X$ modulo the equations in $E$), and ${\eta }_X:X\to TX$ and ${\mu }_X:TTX\to TX$ are given by inclusion of variables and flattening of terms over terms. Then $𝕋$-algebras bijectively correspond to $\mathrm{\Lambda }$-algebras satisfying all equations in $E$, that is, algebras of the variety specified by $(\mathrm{\Lambda },E)$. Monads $𝕋$ induced by finitary algebraic theories are precisely the finitary monads, that is, those preserving directed colimits [3].

Every monad $𝕋$ has a canonical left strength, the natural transformation