Intersection optimization is NP-complete
- 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.
Author details: | Guillaume Bonfante, Joseph Le Roux |
---|---|
URN: | urn:nbn:de:kobv:517-opus-27146 |
Publication type: | Conference Proceeding |
Language: | English |
Publication year: | 2008 |
Publishing institution: | Universität Potsdam |
Release date: | 2008/12/11 |
Organizational units: | Extern / Extern |
DDC classification: | 4 Sprache / 40 Sprache / 400 Sprache |
Collection(s): | Universität Potsdam / Tagungsbände/Proceedings (nicht fortlaufend) / Finite-state methods and natural language processing : 6th International Workshop, FSMNLP 2007 / II Regular Papers |
License (German): | Keine öffentliche Lizenz: Unter Urheberrechtsschutz |
External remark: | The complete edition of the proceedings "Finite-state methods and natural language processing : 6th International Workshop, FSMNLP 2007 ; Revised Papers" is available: URN urn:nbn:de:kobv:517-opus-23812 |