25
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ Just pointing out that the link requires that one can log in to the coursea website. $\endgroup$
    – Dave Clarke
    May 8, 2012 at 6:45
  • 1
    $\begingroup$ What is the partial order that makes regular languages into a poset ? is it merely the subset property ? $\endgroup$
    – Suresh Venkat
    May 8, 2012 at 21:39
  • $\begingroup$ @Suresh Yes, am I missing something? $\endgroup$
    – Alexei Averchenko
    May 9, 2012 at 4:17
  • 1
    $\begingroup$ No. I just wanted to understand if there was something more specific to the language structure $\endgroup$
    – Suresh Venkat
    May 9, 2012 at 16:16
  • $\begingroup$ @Suresh I'm certainly not as smart or educated as people Dave Clarke references, so I only saw the most obvious thing :) $\endgroup$
    – Alexei Averchenko
    May 9, 2012 at 16:18

3 Answers 3

Reset to default
21
$\begingroup$

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

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:

Finally, there's the work on iteration theories, Iteration theories: the equational logic of iterative processes 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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ For automata there's also books.google.co.uk/… $\endgroup$
    – Radu GRIGore
    May 8, 2012 at 11:26
  • 1
    $\begingroup$ 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" 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. $\endgroup$
    – Uday Reddy
    Jun 20, 2012 at 12:17
  • $\begingroup$ Non-paywall link to Bart's paper: repository.ubn.ru.nl/handle/2066/36207 $\endgroup$
    – Turion
    Jul 5, 2019 at 9:34
14
$\begingroup$

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. 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. 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. 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. M. Gehrke, S. Grigorieff, J.-E. Pin.

Improve this answer
$\endgroup$
1
5
$\begingroup$

Looking at the world using category theory goggles is called 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. 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. Locality bimonoids and concurrency is an active research direction.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.