INtersection Optimization is NP-Complete

Guillaume Bonfante 1 Joseph Le Roux 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Type de document :
Communication dans un congrès
Sixth International Workshop on Finite-State Methods and Natural Language Processing - FSMNLP 2007, Sep 2007, Postdam, Germany. 2007
Liste complète des métadonnées

https://hal.inria.fr/inria-00185232
Contributeur : Joseph Le Roux <>
Soumis le : lundi 5 novembre 2007 - 15:34:14
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : lundi 12 avril 2010 - 01:21:20

Fichier

intersection.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00185232, version 1

Collections

Citation

Guillaume Bonfante, Joseph Le Roux. INtersection Optimization is NP-Complete. Sixth International Workshop on Finite-State Methods and Natural Language Processing - FSMNLP 2007, Sep 2007, Postdam, Germany. 2007. 〈inria-00185232〉

Partager

Métriques

Consultations de la notice

141

Téléchargements de fichiers

126