FSA/FST library in Ruby

Hello, Ruby coders,

Though I haven’t found any FSA/FST library
for Ruby on RAA, I still hope it is just not
listed on RAA, or someone is developing it…

Or my hopes are vain?

Yuri Leikind

I have developed a small FST-library half a year ago.

Algorithms implemented:

  1. NFST, construction from RE* (e.g. 'a:b’bbb refers to relation abbb →
    bbbb)
  2. NFST determinization (both Mohri and Roche algorithms)
  3. IsFunctional, determines whether transducer is a rational function
  4. Unambiguous, makes Functional transducer from the NonFunctional one
  5. Superposition calculation
  6. Cascade-based interpreter
  7. Dotty-based output

They were all developed in Ruby and some algorithms are too slow :frowning:
In C they would be much faster.

What I would like to do:

  1. Add a documentation
  2. Implement time-critical algorithms in C
  3. Add minimization algorithms
  4. Add negation
  5. Add lazy implementation where it is possible
  6. Add some compact representation stuff
  7. WFST implementation

It would be nice if some one helped me in this.
Ruby lacks fast regular expressions.

BR,
Sergei

···

----- Original Message -----
From: “Yuri Leikind” leikind@mova.org
Newsgroups: comp.lang.ruby
To: “ruby-talk ML” ruby-talk@ruby-lang.org
Sent: 7 ÏËÔÑÂÒÑ 2002 Ç. 20:52
Subject: FSA/FST library in Ruby

Hello, Ruby coders,

Though I haven’t found any FSA/FST library
for Ruby on RAA, I still hope it is just not
listed on RAA, or someone is developing it…

Or my hopes are vain?

Yuri Leikind