TY  - CONF
A1  - Bonfante, Guillaume
A1  - Le Roux, Joseph
T1  - Intersection optimization is NP-complete
N2  - Finite state methods for natural language processing often require the construction 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 grammars. We show that there is no efficient way to minimize the state complexity of these intersections.
Y1  - 2008
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/2523
UR  - https://nbn-resolving.org/urn:nbn:de:kobv:517-opus-27146
ER  -