Experts

6

7

8

9

10
Publications (26)

1Uniform Recognition for Acyclic ContextSensitive Grammars is NPcomplete1992  Erik Aartsinear t ime contextsensitive grammars recognit ion is NPcomplete even for (some) fixed grammars. l~lrthermore there is a...

2Letting The Cat Out Of The Bag: Generation For ShakeAndBake Mt1992  Chris BrewMachine Translation system.. Since the task itself is NPcomplete, and therefore almost certainly intractable our algorithm...

3Computational Complexity of Probabilistic Disambiguation by means of TreeGrammars1996  Khalil Sima'anleast) as hard as any problem that has been proved to be NPcomplete (i.e. a problem that is known to be decidable on a no...

4A Pathbased Transfer Model for Machine Translation2004  Dekang Linthe Minimum Set Covering Problem is a very wellknown NPComplete problem, the problem of Minimum Path Covering of Trees...

5On the Weak Generative Capacity of Weighted Contextfree Grammars2008  Anders Søgaardproblem for this extension of LIGs can be shown to be NPcomplete by reduction of the vertex cover problem, similar to Søgaard...

6Detecting Multiple Facets of an Event using GraphBased Unsupervised Methodsminimal This task is similar to Minimum Set Cover, which is NPcomplete (Garey and Johnson, 1990). Therefore, trying to find the...

7RTG based surface realisation for TAGwith grammars integrating flat semantics is known to be NP complete. In this paper, we present a new algorithm for surface...

8Unifying Disjunctive Feature Structures1992  Lena Strombackstructures is that the unification operation becomes NPcomplete. Therelore there have been many proposals on how to unify...

9Efficiently Parsing with the ProductFree Lambek Calculus2008  Timothy A. D. Fowler(Moortgat, 1996). Second, the calculus with product is NPcomplete (Pentus, 2006), while the sequent derivability in the ...

10Exploiting Structured Ontology to Organize Scattered Online Opinionssolution of this combinatorial optimization problem is NPcomplete, so we employ a polynomial time greedy algorithm to approximate...