ACL RD-TEC 1.0 Summarization of C92-4183
Paper Title:
UNIFORM RECOGNITION FOR ACYCLIC CONTEXT-SENSITIVE GRAMMARS IS NP-COMPLETE
UNIFORM RECOGNITION FOR ACYCLIC CONTEXT-SENSITIVE GRAMMARS IS NP-COMPLETE
Primarily assigned technology terms:
Other assigned terms:
- approach
- case
- characters
- context-free grammar
- context-free grammars
- context-free language
- context-free languages
- context-sensitive grammar
- derivation
- derivations
- empty string
- fact
- formalism
- generation
- grammar
- grammars
- input string
- lemma
- linear time
- message
- natural language
- natural languages
- np-hard problem
- parse
- polynomial time
- process
- relation
- semantic
- sentence
- sentences
- suffix
- symbol
- symbols
- transitive closure
- trees
- unbounded dependencies
- understanding
- utterance
- word
