INtersection Optimization is NP-Complete

Overview & Synopsis

Finite state methods for natural language processing often require the con- struction and the intersection of several automata. In this paper we investigate the question of determining the best order in which these intersections should be performed. We take as an example lexical disambiguation in polarity gram- mars. We show that there is no efficient way to minimize the state complexity of these intersections.