{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T00:27:31Z","timestamp":1768004851965,"version":"3.49.0"},"reference-count":63,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the smallest grammar problem, we are given a word <jats:italic>w<\/jats:italic> and we want to compute a preferably small context-free grammar <jats:italic>G<\/jats:italic> for the singleton language {<jats:italic>w<\/jats:italic>} (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is <jats:italic>N<\/jats:italic><jats:italic>P<\/jats:italic>-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless <jats:italic>P<\/jats:italic> = <jats:italic>N<\/jats:italic><jats:italic>P<\/jats:italic>. We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains <jats:italic>N<\/jats:italic><jats:italic>P<\/jats:italic>-complete (and its optimisation version is <jats:italic>A<\/jats:italic><jats:italic>P<\/jats:italic><jats:italic>X<\/jats:italic>-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i. e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields <jats:italic>W<\/jats:italic>[1]-hardness. Furthermore, we present an <jats:inline-formula><jats:alternatives><jats:tex-math>$\\mathcal {O}(3^{\\mid {w}\\mid })$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>O<\/mml:mi>\n                  <mml:mo>(<\/mml:mo>\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mo>\u2223<\/mml:mo>\n                      <mml:mi>w<\/mml:mi>\n                      <mml:mo>\u2223<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                  <mml:mo>)<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i. e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the \u201chierarchical depth\u201d of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.<\/jats:p>","DOI":"10.1007\/s00224-020-10013-w","type":"journal-article","created":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T09:09:23Z","timestamp":1605258563000},"page":"344-409","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On the Complexity of the Smallest Grammar Problem over Fixed Alphabets"],"prefix":"10.1007","volume":"65","author":[{"given":"Katrin","family":"Casel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Serge","family":"Gaspers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Gras","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5137-1504","authenticated-orcid":false,"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"10013_CR1","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1613\/jair.374","volume":"7","author":"CG Nevill-Manning","year":"1997","unstructured":"Nevill-Manning, C.G., Witten, I.H.: Identifying hierarchical structure in sequences: A linear-time algorithm. J. Artif. Intell. Res. 7, 67\u201382 (1997)","journal-title":"J. Artif. Intell. Res."},{"key":"10013_CR2","unstructured":"Nevill-Manning, C.G.: Inferring sequential structure, Ph.D. Thesis, University of Waikato, NZ (1996)"},{"key":"10013_CR3","unstructured":"de Marcken, C.: Unsupervised language acquisition. Ph.D. Thesis, Department of Electrical Engineering and Computer Science, MIT, USA (1996)"},{"key":"10013_CR4","unstructured":"Gall\u00e9, M: Searching for compact hierarchical structures in DNA by means of the smallest grammar problem. Ph.D. Thesis, University of Rennes 1, France (2011)"},{"key":"10013_CR5","unstructured":"Lanct\u00f4t, J.K., Li, M., Yang, E.: Estimating DNA sequence entropy. In: Proceedings of the eleventh annual ACM-SIAM symposium on discrete algorithms, SODA 2000, january 9-11, 2000, san francisco, ca, USA., pp. 409\u2013418 (2000)"},{"issue":"3","key":"10013_CR6","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/18.841160","volume":"46","author":"JC Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.-H.: Grammar-based codes: A new class of universal lossless source codes. IEEE Trans. Inf. Theory 46(3), 737\u2013754 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"10013_CR7","doi-asserted-by":"crossref","first-page":"1227","DOI":"10.1109\/18.850665","volume":"46","author":"JC Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.-H., Nelson, G.J., Cosman, P.C.: Universal lossless compression via multilevel pattern matching. IEEE Trans. Inf. Theory 46(4), 1227\u20131245 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"10013_CR8","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1109\/18.841161","volume":"46","author":"E-H Yang","year":"2000","unstructured":"Yang, E.-H., Kieffer, J.C.: Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform - part one: Without context models. IEEE Trans. Inf. Theory 46(3), 755\u2013777 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"10013_CR9","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"JA Storer","year":"1982","unstructured":"Storer, J.A., Szymanski, T.G.: Data compression via textual substitution. Journal of the ACM 29(4), 928\u2013951 (1982)","journal-title":"Journal of the ACM"},{"key":"10013_CR10","unstructured":"Storer, J.A.: NP-completeness results concerning data compression. Tech. Rep. Dept. 234, Electrical Engineering and Computer Science, Princeton University, USA (1977)"},{"key":"10013_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An introduction to Kolmogorov complexity and its applications","author":"M Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P: An introduction to Kolmogorov complexity and its applications, 2nd edn. Springer, Berlin (1997)","edition":"2nd edn."},{"key":"10013_CR12","unstructured":"B\u00f6ttcher, S, Lohrey, M., Maneth, S., Rytter, W.: 08261 abstracts collection - structure-based compression of complex massive data. In: Structure-Based Compression of Complex Massive Data, 22.06. - 27.06.2008. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2008\/1694\/ (2008)"},{"issue":"6","key":"10013_CR13","doi-asserted-by":"publisher","first-page":"22","DOI":"10.4230\/DagRep.3.6.22","volume":"3","author":"S Maneth","year":"2013","unstructured":"Maneth, S., Navarro, G.: Indexes and computation over compressed structured data (dagstuhl seminar 13232). Dagstuhl Reports 3(6), 22\u201337 (2013). https:\/\/doi.org\/10.4230\/DagRep.3.6.22","journal-title":"Dagstuhl Reports"},{"issue":"10","key":"10013_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.4230\/DagRep.6.10.99","volume":"6","author":"P Bille","year":"2016","unstructured":"Bille, P., Lohrey, M., Maneth, S., Navarro, G.: Computation over compressed structured data (dagstuhl seminar 16431). Dagstuhl Reports 6(10), 99\u2013119 (2016). https:\/\/doi.org\/10.4230\/DagRep.6.10.99","journal-title":"Dagstuhl Reports"},{"issue":"2","key":"10013_CR15","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: A survey. Groups, Complexity, Cryptology 4(2), 241\u2013299 (2012)","journal-title":"Groups, Complexity, Cryptology"},{"key":"10013_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4939-0748-9","volume-title":"The compressed word problem for groups","author":"M Lohrey","year":"2014","unstructured":"Lohrey, M.: The compressed word problem for groups, Springer Briefs in Mathematics. Springer, Berlin (2014)","edition":"Springer Briefs"},{"issue":"18-19","key":"10013_CR17","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1016\/j.ipl.2010.07.004","volume":"110","author":"T Akutsu","year":"2010","unstructured":"Akutsu, T.: A bisection algorithm for grammar-based compression of ordered trees. Inf. Process. Lett. 110(18-19), 815\u2013820 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"10013_CR18","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.tcs.2006.07.024","volume":"363","author":"M Lohrey","year":"2006","unstructured":"Lohrey, M., Maneth, S.: The complexity of tree automata and XPath on grammar-compressed trees. Theor. Comput. Sci. 363(2), 196\u2013210 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"10013_CR19","doi-asserted-by":"crossref","first-page":"1150","DOI":"10.1016\/j.is.2013.06.006","volume":"38","author":"M Lohrey","year":"2013","unstructured":"Lohrey, M., Maneth, S., Mennicke, R.: XML tree structure compression using RePair. Inf. Syst. 38(8), 1150\u20131167 (2013)","journal-title":"Inf. Syst."},{"issue":"5","key":"10013_CR20","doi-asserted-by":"crossref","first-page":"1651","DOI":"10.1016\/j.jcss.2012.03.003","volume":"78","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M., Maneth, S., Schmidt-Schau\u00df, M.: Parameter reduction and automata evaluation for grammar-compressed trees. J. Comput. Syst. Sci. 78(5), 1651\u20131669 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"10013_CR21","unstructured":"Gasc\u00f3n, A., Lohrey, M., Maneth, S., Reh, C.P., Sieber, K.: Grammar-based compression of unranked trees. In: Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings, pp. 118\u2013131 (2018)"},{"key":"10013_CR22","unstructured":"Gasc\u00f3n, A., Godoy, G., Schmidt-Schau\u00df, M: Unification with singleton tree grammars. In: Rewriting Techniques and Applications, 20th International Conference, RTA 2009, Bras\u00edlia, Brazil, June 29 - July 1, 2009, Proceedings, pp. 365\u2013379 (2009)"},{"issue":"2","key":"10013_CR23","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1006\/jcss.2002.1852","volume":"65","author":"P Berman","year":"2002","unstructured":"Berman, P., Karpinski, M., Larmore, L.L., Plandowski, W., Rytter, W.: On the complexity of pattern matching for highly compressed two-dimensional texts. J. Comput. Syst. Sci. 65(2), 332\u2013350 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"10013_CR24","unstructured":"Plandowski, W., Rytter, W.: Application of Lempel-Ziv encodings to the solution of words equations. In: Automata, Languages and Programming, 25th International Colloquium, ICALP 1998, Aalborg, Denmark, July 13-17, 1998, Proceedings, pp. 731\u2013742 (1998)"},{"issue":"1","key":"10013_CR25","first-page":"4:1","volume":"63","author":"A Jez","year":"2016","unstructured":"Jez, A.: Recompression: A simple and powerful technique for word equations. J. ACM 63(1), 4:1\u20134:51 (2016)","journal-title":"J. ACM"},{"key":"10013_CR26","unstructured":"Ganardi, M., Jez, A., Lohrey, M.: Balancing straight-line programs. In: 60th Annual Symposium on Foundations of Computer Science, FOCS \u201919, Baltimore, Maryland, USA, November 9-12, 2019 (2019)"},{"issue":"2","key":"10013_CR27","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0166-218X(83)90064-1","volume":"6","author":"B Alspach","year":"1983","unstructured":"Alspach, B., Eades, P., Rose, G.: A lower-bound for the number of productions required for a certain class of languages. Discret. Appl. Math. 6(2), 109\u2013115 (1983)","journal-title":"Discret. Appl. Math."},{"key":"10013_CR28","doi-asserted-by":"crossref","first-page":"895","DOI":"10.1016\/j.ipl.2011.06.006","volume":"111","author":"Y Filmus","year":"2011","unstructured":"Filmus, Y.: Lower bounds for context-free grammars. Inf. Process. Lett. 111, 895\u2013898 (2011)","journal-title":"Inf. Process. Lett."},{"key":"10013_CR29","unstructured":"Bucher, W., Maurer, H.A., II, K.C., Wotschke, D.: Concise description of finite languages. Theor. Comput. Sci. 14, 227\u2013246 (1981)"},{"key":"10013_CR30","unstructured":"Eberhard, S., Hetzl, S.: Compressibility of finite languages by grammars. In: Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings, pp. 93\u2013104 (2015)"},{"key":"10013_CR31","unstructured":"Gruber, H., Holzer, M., Wolfsteiner, S.: On minimal grammar problems for finite languages. In: Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings, pp. 342\u2013353 (2018)"},{"key":"10013_CR32","unstructured":"Holzer, M., Wolfsteiner, S.: On the grammatical complexity of finite languages. In: Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Halifax, NS, Canada, July 25-27, 2018, Proceedings, pp. 151\u2013162 (2018)"},{"issue":"7","key":"10013_CR33","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10013_CR34","unstructured":"Lehman, E.: Approximation algorithms for grammar-based data compression. Ph.D. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology (2002)"},{"issue":"5","key":"10013_CR35","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory 24(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6","key":"10013_CR36","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","volume":"17","author":"TA Welch","year":"1984","unstructured":"Welch, T.A.: A technique for high-performance data compression. IEEE Computer 17(6), 8\u201319 (1984)","journal-title":"IEEE Computer"},{"key":"10013_CR37","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1109\/5.892709","volume":"88","author":"A Apostolico","year":"2000","unstructured":"Apostolico, A., Lonardi, S.: Off-line compression by greedy textual substitution. Proceedings of the IEEE 88, 1733\u20131744 (2000)","journal-title":"Proceedings of the IEEE"},{"key":"10013_CR38","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1109\/5.892708","volume":"88","author":"NJ Larsson","year":"2000","unstructured":"Larsson, N.J., Moffat, A.: Off-line dictionary-based compression. Proceedings of the IEEE 88, 1722\u20131732 (2000)","journal-title":"Proceedings of the IEEE"},{"key":"10013_CR39","unstructured":"Hucke, D., Lohrey, M., Reh, C.P.: The smallest grammar problem revisited. In: String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings, pp. 35\u201349 (2016)"},{"issue":"1-3","key":"10013_CR40","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1-3), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"10013_CR41","unstructured":"Arpe, J., Reischuk, R.: On the complexity of optimal grammar-based compression. In: 2006 data compression conference (DCC 2006), 28-30 march 2006, snowbird, ut, USA, pp. 173\u2013182 (2006)"},{"key":"10013_CR42","volume-title":"Computers and intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. New York: Freeman, New York (1979)"},{"issue":"4","key":"10013_CR43","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/0167-6377(82)90015-3","volume":"1","author":"M Farber","year":"1982","unstructured":"Farber, M.: Independent domination in chordal graphs. Oper. Res. Lett. 1(4), 134\u2013138 (1982)","journal-title":"Oper. Res. Lett."},{"key":"10013_CR44","volume-title":"Computational complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational complexity. Addison-Wesley, Boston (1994)"},{"key":"10013_CR45","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"key":"10013_CR46","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Springer, Berlin (2006)"},{"key":"10013_CR47","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms. Springer, Berlin (2015)"},{"key":"10013_CR48","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation: combinatorial optimization problems and their approximability properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G.: Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer, Berlin (1999)"},{"issue":"3","key":"10013_CR49","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"10013_CR50","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1002\/sapm1949281148","volume":"28","author":"CE Shannon","year":"1949","unstructured":"Shannon, C.E.: A theorem on coloring the lines of a network. Journal of Mathematics and Physics 28, 148\u2013151 (1949)","journal-title":"Journal of Mathematics and Physics"},{"issue":"3","key":"10013_CR51","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.ipl.2005.12.007","volume":"98","author":"S Skulrattanakulchai","year":"2006","unstructured":"Skulrattanakulchai, S.: \u0394-list vertex coloring in linear time. Inf. Process. Lett. 98(3), 101\u2013106 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"1-2","key":"10013_CR52","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1-2), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"10013_CR53","doi-asserted-by":"crossref","first-page":"1745","DOI":"10.1109\/5.892710","volume":"88","author":"CG Nevill-Manning","year":"2000","unstructured":"Nevill-Manning, C.G., Witten, I.H.: On-line and off-line heuristics for inferring hierarchies of repetitions in sequences. Proceedings of the IEEE 88, 1745\u20131755 (2000)","journal-title":"Proceedings of the IEEE"},{"key":"10013_CR54","unstructured":"Benz, F., K\u00f6tzing, T: An effective heuristic for the smallest grammar problem. In: Genetic and Evolutionary Computation Conference, GECCO \u201913, Amsterdam, The Netherlands, July 6-10, 2013, pp. 487\u2013494 (2013)"},{"key":"10013_CR55","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.jda.2011.04.006","volume":"11","author":"R Carrascosa","year":"2012","unstructured":"Carrascosa, R., Coste, F., Gall\u00e9, M, L\u00f3pez, G G I: Searching for smallest grammars on large sequences and application to DNA. Journal of Discrete Algorithms 11, 62\u201372 (2012)","journal-title":"Journal of Discrete Algorithms"},{"key":"10013_CR56","first-page":"311","volume":"15","author":"J-C Fournier","year":"1973","unstructured":"Fournier, J.-C.: Colorations des ar\u00eates d\u2019un graphe. Cahiers Centre \u00c9tudes Recherche Op\u00e9r. 15, 311\u2013314 (1973). Colloque sur la Th\u00e9orie des Graphes (Brussels, 1973)","journal-title":"Cahiers Centre \u00c9tudes Recherche Op\u00e9r."},{"issue":"3","key":"10013_CR57","first-page":"29","volume":"1","author":"VG Vizing","year":"1965","unstructured":"Vizing, V.G.: The chromatic class of a multigraph. Kibernetika (Kiev) 1(3), 29\u201339 (1965)","journal-title":"Kibernetika (Kiev)"},{"issue":"1-3","key":"10013_CR58","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(98)00147-4","volume":"91","author":"DF Manlove","year":"1999","unstructured":"Manlove, D.F.: On the algorithmic complexity of twelve covering and independence parameters of graphs. Discret. Appl. Math. 91(1-3), 155\u2013175 (1999)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"10013_CR59","first-page":"1","volume":"1","author":"JR Griggs","year":"1980","unstructured":"Griggs, J.R., West, D.B.: Extremal values of the interval number of a graph. SIAM Journal on Matrix Analysis and Applications 1(1), 1\u20137 (1980)","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"10013_CR60","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs. Monographs and Textbooks in Pure and Applied Mathematics, vol. 208. Marcel Dekker, New York (1998)"},{"issue":"4-5","key":"10013_CR61","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1016\/j.dam.2012.01.003","volume":"161","author":"N Bourgeois","year":"2013","unstructured":"Bourgeois, N., Croce, F.D., Escoffier, B., Paschos, V.T.: Fast algorithms for min independent dominating set. Discret. Appl. Math. 161(4-5), 558\u2013572 (2013)","journal-title":"Discret. Appl. Math."},{"key":"10013_CR62","first-page":"161","volume":"87","author":"RG Downey","year":"1992","unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. Congressus Numerantium 87, 161\u2013187 (1992)","journal-title":"Congressus Numerantium"},{"key":"10013_CR63","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1137\/S0097539795295663","volume":"28","author":"EG Thurber","year":"1999","unstructured":"Thurber, E.G.: Efficient generation of minimal length addition chains. SIAM Journal on Computing 28, 1247\u20131263 (1999)","journal-title":"SIAM Journal on Computing"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10013-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-020-10013-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10013-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,3]],"date-time":"2021-02-03T09:43:00Z","timestamp":1612345380000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-020-10013-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":63,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["10013"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-10013-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"9 October 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}