<p>Actually, I think what you're looking for is Kleene algebra. See Dexter Kozen's classic article. He gives an axiomatization of Kleene-star. I assume this is the very first step you're interested in.</p>
<blockquote>
<p><a href="https://www.cs.cornell.edu/%7Ekozen/Papers/ka.pdf" rel="nofollow noreferrer">A completeness theorem for Kleene algebras and the algebra of regular events.</a>  Information and Computation, 110(2):366-390, May 1994.</p>
</blockquote>
<p>That article does not use category theory, but it gives an equational axiomatization of Kleene algebras, whose structure includes that of the regular languages. Kleene algebras with tests can be viewed as the extension of regular expressions to model simple programs with loops and conditionals (but without assignments). This extension is useful for reasoning about such simple programs in a purely algebraic manner.</p>
<blockquote>
<p><a href="http://www.cs.cornell.edu/%7Ekozen/papers/ChenPucella.pdf" rel="nofollow noreferrer">On the coalgebraic theory of Kleene algebra with tests.</a> Technical Report. Cornell University, March 2008.</p>
</blockquote>
<p>Regular languages form a Boolean algebra with additional structure, as you observe. This structure has been studied from the viewpoint of Stone duality by Nick Pippenger.</p>
<blockquote>
<p><a href="http://www.springerlink.com/content/fm0gwum3umh4jvre/?MUD=MP" rel="nofollow noreferrer">Regular Languages and Stone Duality</a>. Nicholas Pippenger. Theory Computing Systems, 1997: 121-134.</p>
</blockquote>
<p>The duality approach to language recognition has been in the spotlight recently and has been applied to derive new results about language recognition.</p>
<blockquote>
<p><a href="http://liafa.jussieu.fr/%7Ejep/PDF/DualityWeb.pdf" rel="nofollow noreferrer">Duality and equational theory of regular languages.</a> M. Gehrke, S. Grigorieff, J.-E. Pin.</p>
</blockquote>

CC BY-SA 3.0
2012-05-10T23:11:38.130Z
And specifically about some classic adjunctions of Kleene algebras in machine theory: http://www.cs.cornell.edu/Courses/cs786/2004sp/Lectures/l06-adj.pdf
ex0du5
CC BY-SA 4.0
2012-05-10T07:55:23.847Z
2021-04-26T07:40:17.870Z
2021-04-26T07:40:17.870Z
Vijay D
<p>Looking at the world using category theory goggles is called <a href="http://en.wikipedia.org/wiki/Categorification" rel="noreferrer">categorification</a>.  Sometimes it produces really nice and surprising results.  Physicists have begun to say that thinking of a group as a one-element gropoid makes a really <a href="http://unapologetic.wordpress.com/2007/06/09/groupoids-and-more-group-actions/" rel="noreferrer">big difference</a>.  I am beginning to realize that thinking of a monoid as a one-element category simplifies a lot of things too.  (For instance, a monoid action is then a functor into <strong>Set</strong>. Such things form cartesian-closed categories and toposes.  So, they have a lambda calculus and an intuitionistic logic too!)</p>

<p>You want to categorify regular languages.  I don't know whether it has been done, or done and found to be uninteresting.  I haven't seen anything written about it.  However, the algebraic structure of regular languages, Kleene algebras, is sufficiently interesting.  There is a vast amount of literature on them.  But, in my opinion, the theory of regular languages and finite automata suffers from a premature commitment to finiteness.  (Finite groups are interesting and important, but you don't want the definition of "group" to commit to finiteness at the outset.)  So, it would be useful to throw out finiteness and study the structures more generally.</p>

<p>The most interesting work going on at the moment is related to structures called <strong>locality bimonoids</strong> defined by Hoare.  Concurrent Kleene algebras have been found to be <a href="http://www.springerlink.com/content/6x76827105u6t8n2/" rel="noreferrer">an instance of them</a>.  <a href="http://www.springerlink.com/index/P426725Q333268H8.pdf" rel="noreferrer">Locality bimonoids and concurrency</a> is an active research direction.</p>

CC BY-SA 3.0
2012-06-20T12:09:02.480Z
2012-06-20T12:09:02.480Z
Uday Reddy
<p>There has been a lot done applying category theory to regular languages and automata. One starting point is the recent papers:</p>

<ul>
<li><a href="http://www.springerlink.com/content/287512r87275mk8x/" rel="nofollow noreferrer">Bialgebraic Review of Deterministic Automata, Regular Expressions and Languages</a>
by Bart Jacobs</li>
<li><a href="http://pi.math.cornell.edu/~worthing/bialgebra.pdf" rel="nofollow noreferrer">A Bialgebraic Approach to Automata and Formal Language Theory</a> by James Worthington.</li>
</ul>

<p>In the first of these papers, the structure of regular expressions is treated algebraically and the languages generated are dealt with coalgebraically. These two views are integrated in a bialgebraic setting.  A bialgebra is an algebra-coalgebra pair with a suitable distributive law capturing the interplay between the syntactic terms (the regular expressions) and the computational behaviour (languages generated). The basis of this paper is algebra and coalgebra, as treated in computer science under the umbrellas of universal algebra and coalgebra, rather than what one sees in mathematics (groups etc).</p>

<p>The second paper uses techniques that come from the more traditional mathematical treatment of algebra (modules etc) and coalgebra, but I'm afraid that I don't know the details.</p>

<p>Neither treats Kleene star as an adjunction, as far as I can tell.</p>

<p>More generally, there is a lot of work applying category theory to automata instead of regular expressions. A sample of this work includes:</p>

<ul>
<li><p>Bloom S.L.; Sabadini N.; Walters R.F.C. <a href="http://www.cs.stevens.edu/~bloom/research/pubs2/mmb.pdf" rel="nofollow noreferrer">Matrices, Machines and Behaviors.</a> Applied Categorical Structures, Volume 4, Number 4, December 1996 , pp. 343-360(18)  </p></li>
<li><p>Michael A. Arbib, Ernest G. Manes: <a href="http://www.springerlink.com/content/y650u4451q421573/" rel="nofollow noreferrer">A categorist's view of automata and systems.</a> Category Theory Applied to Computation and Control 1974: 51-64</p></li>
<li><p>M.A. Arbib and E.G. Manes. <a href="http://www.sciencedirect.com/science/article/pii/0022404975900286" rel="nofollow noreferrer">Adjoint machines, state-behaviour machines, and 
duality</a>. Journal of Pure and Applied Algebra, 6:313-344, 1975.</p></li>
<li>M.A. Arbib and E.G. Manes. <a href="http://www.sciencedirect.com/science/article/pii/0022404980900900" rel="nofollow noreferrer">Machines in a category</a>. Journal of Pure and Applied
Algebra, 19:9-20, 1980.</li>
<li>Jirí Adámek and Vera Trnková's book  <a href="http://books.google.co.uk/books?id=MkADy_WxInsC&amp;lpg=PP1&amp;dq=automata%20and%20algebras%20in%20categories&amp;pg=PA82#v=onepage&amp;q&amp;f=false" rel="nofollow noreferrer">Automata and Algebras in Categories</a>, <em>as pointed out in a comment</em>.</li>
</ul>

<p>Finally, there's the work on iteration theories, <a href="http://www.cs.stevens.edu/~bloom/research/bk3.pdf" rel="nofollow noreferrer">Iteration theories: the equational logic of iterative processes</a> by Stephen L. Bloom and Zoltán Ésik, which focusses on iteration (e.g., Kleene star), but from a more general perspective, where regular languages are just one thing that falls under the theory.</p>

CC BY-SA 3.0
2012-05-08T11:26:31.517Z
For automata there's also http://books.google.co.uk/books?id=MkADy_WxInsC&lpg=PP1&dq=automata%20and%20algebras%20in%20categories&pg=PA82#v=onepage&q&f=false
Radu GRIGore
CC BY-SA 3.0
2012-06-20T12:17:08.753Z
Unfortunately, the term "algebra" is overused.  There is the meaning of "algebra" as a generic algebraic structure, which is used in Universal algebra, functor algebras and monad algebras.  The Bart Jacobs paper is talking about those.  There is a more specific structure called "[algebra](http://en.wikipedia.org/wiki/Associative_algebra)" defined in ring/module theory.  James Worthington's paper is dealing with those.  In my opinion, Worthington's work is vastly more interesting, but I think we have only begun to scratch the surface here.
Uday Reddy
CC BY-SA 4.0
2019-07-05T09:34:42.447Z
Non-paywall link to Bart's paper: https://repository.ubn.ru.nl/handle/2066/36207
Turion
CC BY-SA 4.0
2012-05-08T09:33:26.193Z
2019-07-05T15:54:59.447Z
2019-07-05T15:54:59.447Z
Dave Clarke
<p>I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a strict monoidal structure on this category that is distributive over joins (I'm not sure about meets). Is this a useful construct in theory or practice of regular languages? Are there some nice adjunctions to be found, e.g. can we define the Kleene star as one?</p>

<p>This is a copy of a question asked at the Compilers course at Coursera:
<a href="https://class.coursera.org/compilers/forum/thread?thread_id=311">https://class.coursera.org/compilers/forum/thread?thread_id=311</a></p>

CC BY-SA 3.0
2012-05-08T06:45:38.263Z
Just pointing out that the link requires that one can log in to the coursea website.
Dave Clarke
CC BY-SA 3.0
2012-05-08T21:39:55.457Z
What is the partial order that makes regular languages into a poset ? is it merely the subset property ?
Suresh Venkat
CC BY-SA 3.0
2012-05-09T04:17:30.763Z
@Suresh Yes, am I missing something?
Aleksei Averchenko
CC BY-SA 3.0
2012-05-09T16:16:43.480Z
No. I just wanted to understand if there was something more specific to the language structure
Suresh Venkat
CC BY-SA 3.0
2012-05-09T16:18:33.017Z
@Suresh I'm certainly not as smart or educated as people Dave Clarke references, so I only saw the most obvious thing :)
Aleksei Averchenko
CC BY-SA 3.0
2012-05-09T19:48:42.267Z
@AlexeiAverchenko: I'm also not as smart as the people I reference. What I've written is just a starting point. Work has been done in the area since the 70s. I'd be surprised if someone hasn't considered what you suggest.
Dave Clarke
<fl.formal-languages><regular-language><ct.category-theory>
Regular languages from category-theoretical point of view
Aleksei Averchenko
# Regular languages from category-theoretical point of view

(Asked by: username_0 on 2012-05-08)

I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a strict monoidal structure on this category that is distributive over joins (I'm not sure about meets). Is this a useful construct in theory or practice of regular languages? Are there some nice adjunctions to be found, e.g. can we define the Kleene star as one?

This is a copy of a question asked at the Compilers course at Coursera:
<https://class.coursera.org/compilers/forum/thread?thread_id=311>

**Tags:** fl.formal-languages, regular-language, ct.category-theory

> **Comments:**
> **username_1**: Just pointing out that the link requires that one can log in to the coursea website.  
> **username_2**: What is the partial order that makes regular languages into a poset ? is it merely the subset property ?  
> **username_0**: @Suresh Yes, am I missing something?  
> **username_2**: No. I just wanted to understand if there was something more specific to the language structure  
> **username_0**: @Suresh I'm certainly not as smart or educated as people username_1 references, so I only saw the most obvious thing :)  
> **username_1**: @AlexeiAverchenko: I'm also not as smart as the people I reference. What I've written is just a starting point. Work has been done in the area since the 70s. I'd be surprised if someone hasn't considered what you suggest.  

---

## 3 answers

### Answer by username_1 on 2012-05-08. Score: 22 | Accepted answer

There has been a lot done applying category theory to regular languages and automata. One starting point is the recent papers:

* [Bialgebraic Review of Deterministic Automata, Regular Expressions and Languages](http://www.springerlink.com/content/287512r87275mk8x/)
  by Bart Jacobs
* [A Bialgebraic Approach to Automata and Formal Language Theory](http://pi.math.cornell.edu/~worthing/bialgebra.pdf) by James Worthington.

In the first of these papers, the structure of regular expressions is treated algebraically and the languages generated are dealt with coalgebraically. These two views are integrated in a bialgebraic setting. A bialgebra is an algebra-coalgebra pair with a suitable distributive law capturing the interplay between the syntactic terms (the regular expressions) and the computational behaviour (languages generated). The basis of this paper is algebra and coalgebra, as treated in computer science under the umbrellas of universal algebra and coalgebra, rather than what one sees in mathematics (groups etc).

The second paper uses techniques that come from the more traditional mathematical treatment of algebra (modules etc) and coalgebra, but I'm afraid that I don't know the details.

Neither treats Kleene star as an adjunction, as far as I can tell.

More generally, there is a lot of work applying category theory to automata instead of regular expressions. A sample of this work includes:

* Bloom S.L.; Sabadini N.; Walters R.F.C. [Matrices, Machines and Behaviors.](http://www.cs.stevens.edu/~bloom/research/pubs2/mmb.pdf) Applied Categorical Structures, Volume 4, Number 4, December 1996 , pp. 343-360(18)
* Michael A. Arbib, Ernest G. Manes: [A categorist's view of automata and systems.](http://www.springerlink.com/content/y650u4451q421573/) Category Theory Applied to Computation and Control 1974: 51-64
* M.A. Arbib and E.G. Manes. [Adjoint machines, state-behaviour machines, and
  duality](http://www.sciencedirect.com/science/article/pii/0022404975900286). Journal of Pure and Applied Algebra, 6:313-344, 1975.
* M.A. Arbib and E.G. Manes. [Machines in a category](http://www.sciencedirect.com/science/article/pii/0022404980900900). Journal of Pure and Applied
  Algebra, 19:9-20, 1980.
* Jirí Adámek and Vera Trnková's book [Automata and Algebras in Categories](http://books.google.co.uk/books?id=MkADy_WxInsC&lpg=PP1&dq=automata%20and%20algebras%20in%20categories&pg=PA82#v=onepage&q&f=false), *as pointed out in a comment*.

Finally, there's the work on iteration theories, [Iteration theories: the equational logic of iterative processes](http://www.cs.stevens.edu/~bloom/research/bk3.pdf) by Stephen L. Bloom and Zoltán Ésik, which focusses on iteration (e.g., Kleene star), but from a more general perspective, where regular languages are just one thing that falls under the theory.

> **Comments:**
> **username_6**: For automata there's also http://books.google.co.uk/books?id=MkADy_WxInsC&lpg=PP1&dq=automata%20and%20algebras%20in%20categories&pg=PA82#v=onepage&q&f=false  
> **username_5**: Unfortunately, the term "algebra" is overused.  There is the meaning of "algebra" as a generic algebraic structure, which is used in Universal algebra, functor algebras and monad algebras.  The Bart Jacobs paper is talking about those.  There is a more specific structure called "[algebra](http://en.wikipedia.org/wiki/Associative_algebra)" defined in ring/module theory.  James Worthington's paper is dealing with those.  In my opinion, Worthington's work is vastly more interesting, but I think we have only begun to scratch the surface here.  
> **username_7**: Non-paywall link to Bart's paper: https://repository.ubn.ru.nl/handle/2066/36207  

---

### Answer by username_3 on 2012-05-10. Score: 14

Actually, I think what you're looking for is Kleene algebra. See Dexter Kozen's classic article. He gives an axiomatization of Kleene-star. I assume this is the very first step you're interested in.

> [A completeness theorem for Kleene algebras and the algebra of regular events.](https://www.cs.cornell.edu/%7Ekozen/Papers/ka.pdf) Information and Computation, 110(2):366-390, May 1994.

That article does not use category theory, but it gives an equational axiomatization of Kleene algebras, whose structure includes that of the regular languages. Kleene algebras with tests can be viewed as the extension of regular expressions to model simple programs with loops and conditionals (but without assignments). This extension is useful for reasoning about such simple programs in a purely algebraic manner.

> [On the coalgebraic theory of Kleene algebra with tests.](http://www.cs.cornell.edu/%7Ekozen/papers/ChenPucella.pdf) Technical Report. Cornell University, March 2008.

Regular languages form a Boolean algebra with additional structure, as you observe. This structure has been studied from the viewpoint of Stone duality by Nick Pippenger.

> [Regular Languages and Stone Duality](http://www.springerlink.com/content/fm0gwum3umh4jvre/?MUD=MP). Nicholas Pippenger. Theory Computing Systems, 1997: 121-134.

The duality approach to language recognition has been in the spotlight recently and has been applied to derive new results about language recognition.

> [Duality and equational theory of regular languages.](http://liafa.jussieu.fr/%7Ejep/PDF/DualityWeb.pdf) M. Gehrke, S. Grigorieff, J.-E. Pin.

> **Comments:**
> **username_4**: And specifically about some classic adjunctions of Kleene algebras in machine theory: http://www.cs.cornell.edu/Courses/cs786/2004sp/Lectures/l06-adj.pdf  

---

### Answer by username_5 on 2012-06-20. Score: 5

Looking at the world using category theory goggles is called [categorification](http://en.wikipedia.org/wiki/Categorification). Sometimes it produces really nice and surprising results. Physicists have begun to say that thinking of a group as a one-element gropoid makes a really [big difference](http://unapologetic.wordpress.com/2007/06/09/groupoids-and-more-group-actions/). I am beginning to realize that thinking of a monoid as a one-element category simplifies a lot of things too. (For instance, a monoid action is then a functor into **Set**. Such things form cartesian-closed categories and toposes. So, they have a lambda calculus and an intuitionistic logic too!)

You want to categorify regular languages. I don't know whether it has been done, or done and found to be uninteresting. I haven't seen anything written about it. However, the algebraic structure of regular languages, Kleene algebras, is sufficiently interesting. There is a vast amount of literature on them. But, in my opinion, the theory of regular languages and finite automata suffers from a premature commitment to finiteness. (Finite groups are interesting and important, but you don't want the definition of "group" to commit to finiteness at the outset.) So, it would be useful to throw out finiteness and study the structures more generally.

The most interesting work going on at the moment is related to structures called **locality bimonoids** defined by Hoare. Concurrent Kleene algebras have been found to be [an instance of them](http://www.springerlink.com/content/6x76827105u6t8n2/). [Locality bimonoids and concurrency](http://www.springerlink.com/index/P426725Q333268H8.pdf) is an active research direction.


---

