Automata as Categories
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, 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-
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
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)
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.
participants (5)
-
John Maweu -
Juergen Koslowski -
Keith Harbaugh -
Micheal Mac an Airchinnigh -
Steve Stevenson