INtersection Optimization is NP-Complete - Archive ouverte HAL Access content directly
Conference Papers Year : 2007

INtersection Optimization is NP-Complete

(1) , (1)
1

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.
Fichier principal
Vignette du fichier
intersection.pdf (127.25 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive

Dates and versions

inria-00185232 , version 1 (05-11-2007)

Identifiers

  • HAL Id : inria-00185232 , version 1

Cite

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. ⟨inria-00185232⟩
71 View
125 Download

Share

Gmail Facebook Twitter LinkedIn More