[Graph] finite state automata algorithms challenge

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2000-10-25 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: [phone]
----------------------------------------------------------------------

---------- 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.uni-tuebingen.de/~dg/watson_thesis.ps

For transducers, a starting point would be the set of algorithms in
the introduction to the book "Finite-State 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.uni-tuebingen.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 =        "448--458",
}

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                    [phone] office
Section for Computational Linguistics   [phone] home
University of Tuebingen                 Fax: [phone]
Kl. Wilhelmstr. 113
D-72074 Tuebingen, Germany
---------------------------------------------------------------------