Implementation of Dictionaries via Automata and Decision Trees

摘要

Finite-state transducers can be used to map a language onto a set of values. This paper proposes an alternate representation method for such a mapping, consisting of associating a finite-state automaton accepting the input language with a decision tree representing the output values. The advantages of this approach are that it leads to more compact representations than transducers, and that decision trees can easily be synthesized by machine learning techniques.