Factorization of Finite-State Transducers

    •  Emmanuel Roche, "Factorization of Finite-State Transducers", Tech. Rep. TR95-02, Mitsubishi Electric Research Laboratories, Cambridge, MA, January 1995.
      BibTeX TR95-02 PDF
      • @techreport{MERL_TR95-02,
      • author = {Emmanuel Roche},
      • title = {Factorization of Finite-State Transducers},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR95-02},
      • month = jan,
      • year = 1995,
      • url = {}
      • }

Finite-state transducers and finite-state automata are efficient and natural representations for a large variety of problems. We describe a new algorithm for turning a finite-state transducer into the composition of two deterministic finite-state transducers such that the combined size of the derived transducers can be exponentially smaller than other known deterministic constructions. As a consequence, this can also be used to build deterministic representations of finite-state automata smaller than the minimal finite-state automata computed by the classic determinization and minimization algorithms. We also report experimental results on large scale dictionaries and rule-based systems.