
Boost : 
From: Jeremy Siek (jsiek_at_[hidden])
Date: 20001025 08:27:18
Here's an interesting challenge project. Add finite state
automata algorithms to boost, using the boost graph library.

Jeremy Siek www: http://www.lsc.nd.edu/~jsiek/
Ph.D. Candidate email: jsiek_at_[hidden]
Univ. of Notre Dame work phone: (219) 6313906

 Forwarded message 
Date: Wed, 25 Oct 2000 11:45:35 +0200
From: Dale Gerdemann <dg_at_[hidden]>
To: Jeremy Siek <jsiek_at_[hidden]>
Cc: dg_at_[hidden]
Subject: Re: Boost graph class (again)
Hi Jeremy,
It seems to me that your graph class really ought to be tested on a
wider class of algorithms. Given the wealth of algorithms for finite
state automata and transducers, this would be an excellent area for
investigation. I started to do this myself, but my time is very
limited. This seems like the kind of job for a dedicated PhD
student. So I thought I'd write to you in the hope that you'd pass the
idea along to a fellow student.
A starting point would probably be Bruce Watson's thesis, "Taxonomies
and Toolkits of Regular Language Algorithms":
http://www.sfs.nphil.unituebingen.de/~dg/watson_thesis.ps
For transducers, a starting point would be the set of algorithms in
the introduction to the book "FiniteState Language Processing" by
Roche, Shabes and Schabes. This is a good source, which unfortunately
contains a lot of annoying errors. I've tried to compile an errata,
which is available at:
http://www.sfs.nphil.unituebingen.de/~dg/roche_schabes_errata.ps
For learning transducers, there's an interesting algorithm in:
@Article{OncGarVid93,
author = "J. Oncina and P. Garc\'\i{}a and E. Vidal",
title = "Learning subsequential transducers for pattern
recognition interpretation tasks",
journal = "IEEE Transactions on Pattern Analysis and Machine
Intelligence",
year = "1993",
volume = "15",
pages = "448458",
}
The learning algorithm is very tricky to implement efficiently. I'm
sure it would be a terrific challenge to implement it using your graph
class. I've implemented it myself in C++ (using STL) and I have the C
implementation from the authors of the paper.
There are also interesting algorithms for acyclic automata. The
starting point here is Jan Daciuk's PhD thesis:
http://www.pg.gda.pl/~jandac/thesis.ps.gz
And, of course, there are lots of other automata/transducer
algorithms. It would be wonderful (and very useful) to see such
algorithms implemented in a generic framework.

Dale Gerdemann dg_at_[hidden]
Dept. of Linguistics +49 70712974967 office
Section for Computational Linguistics +49 7472442298 home
University of Tuebingen Fax: +49 7071551335
Kl. Wilhelmstr. 113
D72074 Tuebingen, Germany

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk