Finding the smallest binarization of a CFG is NP-hard

作者：

Highlights：

• We show that finding the minimum binarization of a context-free grammar is NP-hard.

• We also provide a lower bound on the approximability of this problem.

• The proof is based on reduction from vertex cover.

• The result also extends to other grammatical formalisms used in NLP.

摘要

•We show that finding the minimum binarization of a context-free grammar is NP-hard.•We also provide a lower bound on the approximability of this problem.•The proof is based on reduction from vertex cover.•The result also extends to other grammatical formalisms used in NLP.

论文关键词：Natural language processing,Complexity,Binarization,Grammars,Context-free grammar,Parsing

论文评审过程：Received 10 June 2012, Revised 25 September 2013, Accepted 19 December 2013, Available online 2 January 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.12.003