Recognizing Collapsing Words is co-NP-Complete.
Alessandra CherubiniAndrzej KisielewiczPublished in: DCFS (2006)
Keyphrases
- np complete
- randomly generated
- np hard
- satisfiability problem
- computational complexity
- keywords
- phase transition
- conjunctive queries
- word sense disambiguation
- databases
- polynomial time complexity
- np complete problems
- n gram
- text documents
- automatic recognition
- related words
- syntactic categories
- text mining
- document representation
- data complexity
- bounded treewidth
- search algorithm
- english words
- data sets