Re: Automata as Categories

Re: Automata as Categories

[Juergen Koslowski]

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)

Re: Automata as Categories

[Keith Harbaugh]

A textbook (unfortunately long out of print)
that seems quite suitable in both content and level
to your need is:

Ehrig, Kiermeier, Kreowski and K\:uhnel
Universal Theory of Automata
Teubner, 1974, 240pp.

Also, in response Juergen's remark that
"classical automata theory" is a rather horrible mess,
one most distinguished categorist evidently agreed with him
and responded by writing two ~400 page books on the subject:

Samuel Eilenberg
Automata, Languages and Machines
Academic Press, 1974 and 1976.

They make no explicit use of categorical notions nor language,
but considering the author and date the categorical spirit
surely prevails.
Note also his book with Elgot on Recursiveness.

Best, Keith


>From: Steve Stevenson <steve@cs.clemson.edu>
>To: categories@mta.ca
>Subject: categories: Automata as Categories
>Date: Tue, 20 May 2003 11:15:23 -0400 (EDT)

>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.

re: Automata as Categories

[Micheal Mac an Airchinnigh]

At 11:15 -0400 2003/20/05, Steve Stevenson wrote:
>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.
>
>Thanks in advance...
>
>steve
---
Hi Steve!

In my opinion, you're looking for stuff
on M-categories (M a Monoid)
and you're searching under keywords
like "action" --- initially left!

There is good material in Barr & Wells 1999.
(The 3rd edition)

or better groundwork ---
Lawvere and Rosebrugh 2003
[ though much of what you
eventually need is in the exercises :) ]

Micheal

--
          ... o O o O o ...
USUK WAR ON UN 20030320+...
USUK WAR PART II 20030501+...
          ... o O o O o ...
---
Mícheál Mac an Airchinnigh
5 Parson's Street
Maynooth, Co. Kildare, Ireland
mailto:micheal1@mac.com
mailto:mmaa@eircom.net

re: Automata as Categories

[John Maweu]

Hi,

On Tue, 20 May 2003, Steve Stevenson wrote:

>
> 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.
>
> Thanks in advance...
>
> steve
>

	Are you looking for more than the examples in Arrows, Structures,
and Functors by Arbib and Manes?
-o-

Automata as Categories

[Steve Stevenson]

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.

Thanks in advance...

steve