Smaller Automata

Another motivation for the introduction of predicates is the observation that the resulting automata are smaller. The size of automata is an important problem in practice [5,21]. With predicates, potentially large sets of transitions are replaced by a single transition. For example, if an automaton has transitions from state p to state q over all ASCII symbols except for a symbol a, for which there is a transition from p to r, then there are 128 transitions leaving p. Using predicates, there are only two transitions leaving p (one labeled by a predicate $\{\mbox{\tt a}\}$, and one labeled by $\overline{\{\mbox{\tt a}\}}$). But note that similar space reductions can be achieved using failure transitions and related techniques [24,21,6,22].

More interesting space reductions can be achieved in the case of transducers. The introduction of predicates with identity not only leads to transducers with fewer transitions, but also to transducers that have fewer states. This observation will be discussed in section 3.7. In section 4.2 we show that this space reduction is achieved for linguistically relevant examples too.

The implementation of various operations is faster for smaller automata. Although the implementation of some of the relevant operations becomes somewhat more complex, it is our experience that in almost all cases overall performance improves considerably.