Re: [Graph] finite state automata algorithms challenge

From: Daryle Walker (darylew_at_[hidden])
Date: 2000-10-25 12:49:20

on 10/25/00 8:27 AM, Jeremy Siek at jsiek_at_[hidden] wrote:

> Here's an interesting challenge project. Add finite state
> automata algorithms to boost, using the boost graph library.

I was thinking of adding something related, state machines, to Boost.  It
would be based on the article "State Machine Design in C++" by David
Lafreniere for the May 2000 issue of the _C/C++ Users Journal_.  I haven't
done too much with it because:

1.  I'm too busy doing other stuff for Boost, like the math stuff
2.  I couldn't think of any test examples.
3.  I don't know whether or not to use your graph stuff.  I think it can let
me assign states and transitions to items (properties to nodes and edges,
respectively).  But I'm not sure if it can help with single transversals.
Another problem is that the sub-library is big; I may not want to drag a lot
of baggage for a specialized field.  Making custom graph stuff (maybe with
std::map's) could be easier.

I wonder: if someone does your project, or if I do mine, could the regex guy
use it for a new implementation?

P.S.  Your forwarded messages mentioned some papers (listed below).  Are
they available in PDF format?

http://www.sfs.nphil.uni-tuebingen.de/~dg/watson_thesis.ps
http://www.sfs.nphil.uni-tuebingen.de/~dg/roche_schabes_errata.ps
http://www.pg.gda.pl/~jandac/thesis.ps.gz

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com