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: | Guillaume Bonfante, Joseph Le Roux |
|---|---|
| URN: | urn:nbn:de:kobv:517-opus-27146 |
| Document Type: | Conference Proceeding |
| Language: | English |
| Year of Completion: | 2008 |
| Publishing Institution: | Universität Potsdam |
| Release Date: | 2008/12/11 |
| Organizational units: | Extern / Extern |
| Dewey Decimal Classification: | 4 Sprache / 40 Sprache / 400 Sprache |
| Collections: | Universität Potsdam / Tagungsbände/Proceedings (nicht forlaufend) / Finite-state methods and natural language processing : 6th International Workshop, FSMNLP 2007 / II Regular Papers |
| Licence (German): |  Keine Nutzungslizenz vergeben - es gilt das deutsche Urheberrecht |
| Notes extern: | 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 |
