Kleene Categories (was: Automata vs. Categories)
sci.math
September, 2001
 
Ugo Dal Lago <dallago@sci.uniud.it> wrote in message news:<3B8A0F57.CBF9124B@sci
.uniud.it>...
> The question is:
> Is there any way to see classes of automata (finite, pushdown, TM,...)
> as categories? Which kind of morphisms should we use as arrows?
 
I'll address your question throughout this article in detail below.
 
Consider this.
 
An abstract Kleene algebra is a partially ordered monoid M in which
the following are true:
 
(A) Every finite subset of M has a least upper bound sup(M)
(B) If M1, M2 are finite subsets of M then
            sup(M1) sup(M2) = sup(M1 M2)
    where M1 M2 = { m1 m2: m1 in M1, m2 in M2 }
(C) There is an operation a |-> a* defined on M such that:
    1 + a a* <= a*
    a + bx + xc <= x --> b* a c* <= x
 
where <= is the partial ordering.
 
This will generalise to categories.
 
Axioms (A) and (B), alone, defined a DIOID.  If they are extended to
allow arbitrary sets for M1 and M2 instead of finite subsets, then the
resulting structure is a QUANTALE.  In a quantale, an operation x* can
then be defined as sup{1,x,xx,xxx,xxxx,...} which satisfies the above
properties.
 
The standard interpretation is as regular expressions.  Let M be any monoid
then R(M) is the set of rational subsets of M.  These are the subsets formed
from the finite subsets of M by application of the operations:
 
         Products: UV = { uv: u in U, v in V }
         Unions: U+V = U union V
         Stars: U* = submonoid of M generated by U = {1}+U+UU+UUU+...
 
A regular expression is an element of R(X*), where X* denotes the free
monoid generated by X (= the set of all finite sequences over X).
 
The axioms above are complete in the sense that every identity in R(X*)
is provable.  (Proof of completeness can be found among one of the
articles in http://www.csd.uwm.edu/~whopkins; where I also talk in
several places on the deep-rooted analogous link which exists
between formal language and automata theory vs. Quantum Field Theory;
as I'll also discuss below).
 
The more general category-theoretic definition would read like so:
 
A Kleene Category C is a category in which
(A) Every homset C(A,B) is partially ordered such that every finite
    subset has a least upper bound.
(B) If U1, U2 are finite subsets of C(A2,A3) and C(A1,A2) then
    sup(U1) sup(U2) = sup(U1 U2)
(C) There is an operation f |-> f* defined over each homset C(A,A),
    such that:
                1_A + f f* <= f*
                if u + xv + wx <= x then w* u v* <= x
 
where in the latter inequality, u: A -> B, v: A -> A, w: B -> B, x: A -> B.
 
A similar completeness theorem for Kleene Categories will exist.  Only
this time, in place of X you have a GRAPH G (= state diagram).  In place
of X* you have Cat(G), the the CATEGORY GENERATED BY G (= a product closure
of G).  In place of R(M) you have R(C), the rational closure of a category
C (similar to the concept of rationally closing an automaton by
incorporating all arrows e: A -> B for regular expressions e).
 
The completeness theorem then states that the theory of Kleene categories
will characterize all identities over R(Cat(G)).
 
An automaton is equivalent to a rational category with an initial object I
and final object F.  If G is a graph which generates the category, then G
is the automaton's state diagram.
 
Another key point is that matrix algebras can be formed over a Kleene
algebra K.  If I is a N-row-vector, F a N-column vector and H an NxN
matrix, then I H* F will be the expression 'recognized' by the automaton
which has an initial object I, final object F, and N objects with
transitions:
               I --> I[n] --> [n]
              [m] --> H[m,n] --> [n]
              [n] --> F[n] --> F
 
The rational closure of this graph is an automaton in which
                     I H* F: I -> F
and, in fact,
               sup Hom(I, F) = I H* F
 
H is analogous to the (interaction) "Hamiltonian" of a system, I is the
"initial state", F, the "final state", S = H* the "S-matrix" and the
expression (valid in Quantales)
 
                 S = 1 + H + HH + HHH + HHHH + ....
 
analogous to Dyson's formula which expresses the S matrix in terms of
the (interaction) Hamiltonian.
 
The non-square matrices of a Kleene algebra K, together, comprise a Kleene
category, which I defined as K*.
 
The notion of matrix algebra can also be generalised to Kleene categories.
Let C be a Kleene category.  Then defined C* as follows:
 
          Ob(C*) = Ob(C)*
 
with morphisms:
 
          M: (A1,A2,...,Am) -> (B1,B2,...,Bn)
 
if M is a (m X n) matrix consisting of morphisms M_uv: Au -> Bv, for all
u = 1, 2, ..., m and v = 1, 2, ..., n.
 
Then C* is a Kleene Category.
 
This has an intimate link that can be expressed in terms of the formal
Bra-Ket algebra:
 
Cn: defined as the Kleene algebra generated from the set of formal symbols
    <0|, <1|, ..., <n-1|, |0>, |1>, ..., |n-1>
 
subject to the identities
 
    <i| |j> = delta_{ij}; |0><0| + |1><1| + ... + |n-1><n-1| = 1
 
A similar object is defined in the theory of Quantales or any other
theory which has a semiring structure.
 
This algebra is isomorphic to its n x n matrix algebra.  Therefore, it
contains with it an entire copy of (Cn)*.
 
The algebra C2 which sits inside the theory of quantales allows you to
represent arbitrary automata in terms of rational categories.  Just as
there is an equivalence theorem relating finite state automata to
regular expressions, there is also an equivalence theorem relating
automata constructed over certain algebras defined with C2 to
push down automata and Turing machines.