Boost logo

Boost :

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:
 Ph.D. Candidate email: jsiek_at_[hidden]
 Univ. of Notre Dame work phone: (219) 631-3906

---------- 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":

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:

For learning transducers, there's an interesting algorithm in:

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

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 7071-29-74967 office
Section for Computational Linguistics +49 7472-442298 home
University of Tuebingen Fax: +49 7071-551335
Kl. Wilhelmstr. 113
D-72074 Tuebingen, Germany

Boost list run by bdawes at, gregod at, cpdaniel at, john at