Finding the smallest binarization of a CFG is NP-hard
From MaRDI portal
Publication:2637648
DOI10.1016/j.jcss.2013.12.003zbMath1285.68084OpenAlexW2076801904MaRDI QIDQ2637648
Publication date: 13 February 2014
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2013.12.003
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Context-free grammars: covers, normal forms, and parsing
- On parsing coupled-context-free languages
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Independent parallelism in finite copying parallel rewriting systems
- On certain formal properties of grammars
- The Smallest Grammar Problem
- An Improved Context-Free Recognizer
- Data compression via textual substitution
- Reducibility among Combinatorial Problems
- Recognition and parsing of context-free languages in time n3
- An efficient context-free parsing algorithm