Abstract:

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.