Directory of Finite State Transducers Resources

Home > Computers > Computer Science > Theoretical > Automata Theory > Finite State Transducers

Transducers are automata that have transitions labeled with two symbols. One of the symbols represents input, the other output. Transducers translate (or transduce) strings. In automata theory they are called Mealy machines. Finite state transducers recognize tuples of strings. A set of tuples of strings that can be recognized by an FST is called a regular relation. So, regular relations are to FSTs what regular languages are to FSA.

Resources in This Category

• Applications of Finite-State Transducers in Natural-Language Processing

  http://www2.parc.com/istl/members/karttune/publications/ciaa-2000/fst-in-nlp.pdf#search="finite state transducers"
  A paper reviewing some of the major applications of FST in natural-language processing ranging from morphological analysis to finite-state parsing.

• Finite State Parsers and Transducers

  http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/
  Lecture notes on FST and their use in building parsers with examples implemented in Prolog.

• Finite State Transducers

  http://www.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan.Daciuk/personal/thesis/node13.html
  Definition of FST with examples of simple transducers.

• Finite State Transducers

  http://en.wikipedia.org/wiki/Finite_state_transducer
  Wikipedia article with a formal definition and discussion of operators on FST.

• Finite-state Transducers

  http://www.cs.sfu.ca/~anoop/courses/MACM-300-Spring-2006/fst.pdf#search="finite state transducers"
  A set of slides on finite state transducers, their connection to regular relations and examples of their closure properties.

• Parsing With Finite State Transducers

  http://www.merl.com/reports/docs/TR96-30.pdf
  A paper that shows how FST can be used to describe complex sytactic structures and provide tools to increase parsing efficiency.

 

Home > Computers > Computer Science > Theoretical > Automata Theory > Finite State Transducers

 

---

 

Thanks to DMOZ, which built a great web directory for nearly two decades and freely shared it with the web. About us