Talk:Smallest grammar problem

Possible CoI in reference editing

On this page, I would like to update the reference to NP-completeness in two ways: (1) IMHO, the proper reference to the first NP-hardness proof of Grammar-based Compression is: @TECHREPORT{Sto77, AUTHOR = "James A. Storer", TITLE = "{NP}-Completeness Results Concerning Data Compression", INSTITUTION = "Dept. Electrical Engineering and Computer Science, Princeton University, USA", YEAR = 1977, month = nov, number = "234", } (2) As this hardness result was later also misinterpreted as to work with finite alphabets, I also suggest referring to: @article{CasFGGS2021,

author = {Katrin Casel and Henning Fernau and Serge Gaspers and Benjamin Gras and Markus L. Schmid},
 title     = {On the Complexity of the Smallest Grammar Problem over Fixed Alphabets},
 journal   = {Theory of Computing Systems},
 volume    = {65},
 number    = {2},
 pages     = {344--409},
 year      = {2021},

} but here I have an obvious CoI, so I need your advice. HenningFernau (talk) 13:32, 14 March 2026 (UTC)