Algebraic Foundation For Formal Language Theory I

From: Mark Hopkins (whopkins_at_alpha2.csd.uwm.edu)
Date: 05/20/04 

Date: 20 May 2004 17:49:43 GMT

The following articles are some writeups that were generated during an
e-mail exchange. I haven't edited the letters very much, but the few
mistakes that crept up in earlier ones were noted and corrected in later
letters. Others have been rectified, so the letters don't exactly
match the original e-mail.

The "web site" mentioned in the letters is currently at:
           http://www.uwm.edu/~whopkins/compalg/index.html
representing some earlier USENET posting, notes and writeups in various
states of completion. Of particular interest are:
   A Purely Algebraic Formulation and Proof of Parikh's Theorem
   --- a "fixed point" theorem for commutative Kleene algebras
       (cKA's) introduces a formal "calculus" structure on cKA's
       complete with the analogous theorems (e.g. Taylor's
       Theorem).
   In the IEEE '99 proceedings on Logic in Computer Science.

   Kleene Algebras and Regular Expressions
   --- a proof of the algebraic Kleene theorem

   Dioids, Quantales and Kleene Algebras
   --- an algebraic rendition of the AFL concept.

   Kleene Categories And Automata
   --- introduces the Kleene algebraic analogue of a "groupoid"

   Formal Language And Automata Theory
   --- contains numerous additional expositories and writeups

           Monads, Analytic Dioids and Power Series
            --- algebraic generalization of the AFL concept.

In time, there should be more formal writeups at the site containing
these articles.

=============

Part I: Context Free Expressions With Dirac Notation

>From May 5:

The idea of using the bra-ket notation in formal language theory originated
with me. The closest analogue in the published literature is the polycyclic
algebras, which are defined analogously. Polycyclic algebras, I believe,
reside in semigroup theory, but other algebraic categories admit such an
object (e.g. a polycyclic ring). A more interesting object would be a
polycyclic groupoid. The polycyclic algebra I'm using the bra-ket notation
to denote resides within the category of Kleene algebras.

I came up with the idea of defining context free expressions by embedding
the Kleene algebra of regular expressions within a larger Kleene algebra
that also contains a polycyclic subalgebra. There is no prior reference
to the concept, as far as I'm aware. The key theorem (which, by the way,
I still haven't found the adequate formulation of or proof for) is
something to the effect:
                    C(M) = Z_{P_n}(R(M) x P_n) for all n > 1,
where R(M), C(M) are the algebras of regular and context free subsets of
a monoid M; P_n the polycyclic algebra on n generators; and Z_A(...)
denotes the subalgebra { k in ...: ka = ak for a in A }. So, context
free expressions are bra-ket expressions that commute with the subalgebra
P_n.

The tensor product K x L for algebras K, L is the universal object that
embeds K and L via eta_K: K -> KxL, eta_L: L -> KxL such that
eta_K(k) eta_L(l) = eta_L(l) eta_K(k) -- i.e., KxL is the free extension
of K and L in which K and L commute with each other.

This object exists in any algebraic category that has a product operation
and generalizes the concept of tensor product familiar in the theory of
linear algebras. But there is no prior reference to this concept anywhere
in the published literature I'm aware of either.

The point I wanted to make about the characterization:
                   C(M) = Z_{P_n}(R(M) x P_n), n > 1
is that this is just the algebraic rendition of the Chomsky-Schuetzenberger
representation theorem for context-free languages. The problem with
finding the proper algebraic formulation (and proof) for it is

            (a) determining which algebra this theorem resides in
            (b) generalizing it replacing R(M) by an arbitrary object K
                and C(M) by closure(K), which denotes the closure of
                K under least fixed point solutions to "grammars".