Standard Kleene algebras --- Precise definition and categorical interpretation

60 Views Asked by At

On page 27 of Conway's book ``Regular Algebra and Finite Machines'', a Standard Kleene Algebra is defined rather loosely as

1

It seems that the $\sum$ operation is in reality a collection of operations: for every set $T$ a map $\sum_T:S^T\to S$ that takes a family of Elements $\mathbf{E}=(E_t)_{t\in T}$ to an element $\sum_T\mathbf{E}\in S$, alternatively written as $\sum_{t\in T}E_t$ and subject to some implicit assumptions (such as invariance under permutation of the indices and $\sum_\emptyset\emptyset=0$).

I find this somewhat unsatisfying. It seems that one should (?) alternatively define a single operation $\sum:2^S\to S,A\mapsto\sum_A$ (and to allow the notation $\sum_A = \sum_{a\in A}a$) such that

  1. $\sum_\emptyset=0$
  2. $\sum_{\{s\}}=s$ for all $s\in S$
  3. for any set $\mathcal{A}\subset 2^S$, setting $\bigcup\mathcal{A}=\bigcup_{A\in\mathcal{A}}A\in 2^S$ and $\sum_\mathcal{A}=\{\sum_A\mid A\in\mathcal{A}\}\in 2^S$, $$\sum{}_{\bigcup\mathcal{A}} = \sum{}_{\sum_\mathcal{A}}$$
  4. For $A, B\in 2^S$, setting $A\cdot B=\{a\cdot b\mid a\in A, b\in B\}\in 2^S$, $$\sum{}_{A}\cdot\sum{}_{B}=\sum{}_{A\cdot B}$$

And then define, for any set $T$ and any family $\mathbf{E}=(E_t)_{t\in T}\in S^T$, $\sum_T\mathbf{E}=\sum_{t\in T}E_t := \sum_{\mathrm{Ran}(\mathbf{E})}$ where $\mathrm{Ran}(\mathbf{E})=\{E_t\mid t\in T\}$

Question 1. Is there an advantage to Conway's formulation of the axiomatics of Standard Kleene Algebras over the above ?

Points 2. and 3. mean that the map $\sum:2^S\to S$ makes $S$ an algebra over the powerset monad (which isn't surprising since one of the early propositions in Conway's text is that $S$ is a complete lattice)

Question 2. What is the categorical interpretation of multiplication $\cdot$ and of the Kleene star operator $*$ ?

Question 3. More broadly, is there a neat categorical definition of Standard Kleene Algebras that may make sense in other categories than $\textbf{Set}$? Is there a good source on this point of view?

With respect to question 3 I only have vague guesses. Since Conway's S3 and S4 mean that $(S,\cdot)$ is a monoid, S5 is a compatibility condition with the powerset-monad algebra structure $\sum$. It seems that the star construction is then a sort of ``free monoid construction within $(S,\sum)$'', if that makes any sense.