Re: Automata as Categories

[Juergen Koslowski <koslowj@iti.cs.tu-bs.de>]

Steve Stevenson <steve@cs.clemson.edu> asked

> I am interested to find an article or book that is a category-
> theoretic redevelopment of "classical" automata. I'd like to find
> something that graduate students could use if they had already had an
> automata course and now would retrace that same development using
> category-theoretic vocabulary and means.

Dear Steve,

I'd be interested in such pointers as well, especially since "classical
automata theory" is a rather horrible mess.  You may want to check out

- Edwin Stewart Bainbridge's thesis "A unified minimal realization theory
  with duality", PhD Thesis, U. of Michigan, 1972.

- R. Betti, "Automi e categorie chiuse" Boll. Un. Mat. Ital. A (5)\(1980),
  44--58

- Kasangian, Kelly, and Rossi "Cofibrations and the realization of
  non-deterministic automata", Cahiers Topologie Geom. Diff. 24, 1 (1983),
  23--46.

Also, Mark William Hopkins presents some interesting ideas on his
WEB-page <http://www.uwm.edu/~whopkins/compalg/index.html>.  A pointer
to the coalgebraic view of automata is Jan Rutten's page
<http://homepages.cwi.nl/~janr/papers>.  You may want to start with
"Automata and coinduction (an exercise in coalgebra). Technical Report
SEN-R9803", which is available for downloading.

Cheers,

-- Juergen

-- 
Juergen Koslowski               If I don't see you no more on this world
ITI, TU Braunschweig               I'll meet you on the next one
koslowj@iti.cs.tu-bs.de               and don't be late!
http://www.iti.cs.tu-bs.de/~koslowj      Jimi Hendrix (Voodoo Child, SR)