{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:13Z","timestamp":1759638853451,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540857792"},{"type":"electronic","value":"9783540857808"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-85780-8_5","type":"book-chapter","created":{"date-parts":[[2008,9,9]],"date-time":"2008-09-09T05:23:54Z","timestamp":1220937834000},"page":"72-83","source":"Crossref","is-referenced-by-count":22,"title":["The Frobenius Problem and Its Generalizations"],"prefix":"10.1007","author":[{"given":"Jeffrey","family":"Shallit","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"206","DOI":"10.2307\/2321610","volume":"87","author":"R. Alter","year":"1980","unstructured":"Alter, R., Barnett, J.A.: A postage stamp problem. Amer. Math. Monthly\u00a087, 206\u2013210 (1980)","journal-title":"Amer. Math. Monthly"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Beihoffer, D., Hendry, J., Nijenhuis, A., Wagon, S.: Faster algorithms for Frobenius numbers. Elect. J. Combinatorics\u00a012(1) (2005), Paper R27, \n                      http:\/\/www.combinatorics.org\/Volume_12\/Abstracts\/v12i1r27.html","DOI":"10.37236\/1924"},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"299","DOI":"10.2307\/2371684","volume":"64","author":"A. Brauer","year":"1942","unstructured":"Brauer, A.: On a problem of partitions. Amer. J. Math.\u00a064, 299\u2013312 (1942)","journal-title":"Amer. J. Math."},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M. Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci.\u00a047, 149\u2013158 (1986); Errata 302, 497\u2013498 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1006\/jnth.1994.1071","volume":"48","author":"J.L. Davison","year":"1994","unstructured":"Davison, J.L.: On the linear diophantine problem of Frobenius. J. Number Theory\u00a048, 353\u2013363 (1994)","journal-title":"J. Number Theory"},{"key":"5_CR6","first-page":"15","volume":"7","author":"D. Einstein","year":"2007","unstructured":"Einstein, D., Lichtblau, D., Strzebonski, A., Wagon, S.: Frobenius numbers by lattice point enumeration. Integers\u00a07, A15 (2007) (electronic)","journal-title":"Integers"},{"key":"5_CR7","first-page":"407","volume":"10","author":"K. Ellul","year":"2005","unstructured":"Ellul, K., Krawetz, B., Shallit, J., Wang, M.-w.: Regular expressions: new results and open problems. J. Autom. Lang. Combin.\u00a010, 407\u2013437 (2005)","journal-title":"J. Autom. Lang. Combin."},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0196-6774(88)90025-9","volume":"9","author":"H. Greenberg","year":"1988","unstructured":"Greenberg, H.: Solution to a linear Diophantine equation for nonnegative integers. J. Algorithms\u00a09, 343\u2013353 (1988)","journal-title":"J. Algorithms"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/0022-0000(85)90042-X","volume":"31","author":"J. Incerpi","year":"1985","unstructured":"Incerpi, J., Sedgewick, R.: Improved upper bounds on shellsort. J. Comput. System Sci.\u00a031, 210\u2013224 (1985)","journal-title":"J. Comput. System Sci."},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1007\/3-540-52048-1_47","volume-title":"Proc. 9th Conf. Found. Software Tech. Theor. Comput. Sci.","author":"R. Kannan","year":"1989","unstructured":"Kannan, R.: Solution of the Frobenius problem. In: Veni Madhavan, C.E. (ed.) Proc. 9th Conf. Found. Software Tech. Theor. Comput. Sci. LNCS, vol.\u00a0405, pp. 242\u2013251. Springer, Heidelberg (1989)"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF01204720","volume":"12","author":"R. Kannan","year":"1992","unstructured":"Kannan, R.: Lattice translates of a polytope and the Frobenius problem. Combinatorica\u00a012, 161\u2013177 (1992)","journal-title":"Combinatorica"},{"key":"5_CR12","unstructured":"Kao, J.-Y., Shallit, J., Xu, Z.: The Frobenius problem in a free monoid. In: Albers, S., Weil, P. (eds.) STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Dagstuhl Seminar Proceedings, Germany, pp. 421\u2013432 (2008)"},{"key":"5_CR13","first-page":"1266","volume":"194","author":"A.N. Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk. SSSR\u00a0194, 1266\u20131268 (1970); In Russian. English translation in Soviet Math. Dokl. 11, 1373\u20131375 (1970)","journal-title":"Dokl. Akad. Nauk. SSSR"},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF01300131","volume":"16","author":"J.L. Ram\u00edrez-Alfons\u00edn","year":"1996","unstructured":"Ram\u00edrez-Alfons\u00edn, J.L.: Complexity of the Frobenius problem. Combinatorica\u00a016, 143\u2013147 (1996)","journal-title":"Combinatorica"},{"key":"5_CR15","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198568209.001.0001","volume-title":"The Diophantine Frobenius Problem","author":"J.L. Ram\u00edrez-Alfons\u00edn","year":"2005","unstructured":"Ram\u00edrez-Alfons\u00edn, J.L.: The Diophantine Frobenius Problem. Oxford University Press, Oxford (2005)"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"465","DOI":"10.2307\/2032755","volume":"7","author":"J.B. Roberts","year":"1956","unstructured":"Roberts, J.B.: Note on linear forms. Proc. Amer. Math. Soc.\u00a07, 465\u2013469 (1956)","journal-title":"Proc. Amer. Math. Soc."},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jsc.2007.06.002","volume":"43","author":"B.H. Roune","year":"2008","unstructured":"Roune, B.H.: Solving thousand-digit Frobenius problems using Gr\u00f6bner bases. J. Symbolic Comput.\u00a043, 1\u20137 (2008)","journal-title":"J. Symbolic Comput."},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0196-6774(86)90001-5","volume":"7","author":"R. Sedgewick","year":"1986","unstructured":"Sedgewick, R.: A new upper bound for shellsort. J. Algorithms\u00a07, 159\u2013173 (1986)","journal-title":"J. Algorithms"},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/BF01932703","volume":"29","author":"E.S. Selmer","year":"1989","unstructured":"Selmer, E.S.: On shellsort and the Frobenius problem. BIT\u00a029, 37\u201340 (1989)","journal-title":"BIT"},{"issue":"1","key":"5_CR20","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1145\/507457.507473","volume":"33","author":"J. Shallit","year":"2002","unstructured":"Shallit, J.: The computational complexity of the local postage stamp problem. SIGACT News\u00a033(1), 90\u201394 (2002)","journal-title":"SIGACT News"},{"issue":"2","key":"5_CR21","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/BF02984830","volume":"25","author":"J. Shallit","year":"2003","unstructured":"Shallit, J.: What this country needs is an 18-cent piece. Math. Intelligencer\u00a025(2), 20\u201323 (2003)","journal-title":"Math. Intelligencer"},{"key":"5_CR22","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/368370.368387","volume":"27","author":"D.L. Shell","year":"1959","unstructured":"Shell, D.L.: A high-speed sorting procedure. Commun. ACM\u00a027, 30\u201332 (1959)","journal-title":"Commun. ACM"},{"key":"5_CR23","first-page":"119","volume":"5","author":"J.J. Sylvester","year":"1882","unstructured":"Sylvester, J.J.: On subinvariants, i.e. semi-invariants to binary quantics of an unlimited order. Amer. J. Math.\u00a05, 119\u2013136 (1882)","journal-title":"Amer. J. Math."},{"key":"5_CR24","volume-title":"Computational Recreations in Mathematica","author":"I. Vardi","year":"1991","unstructured":"Vardi, I.: Computational Recreations in Mathematica. Addison-Wesley, Reading (1991)"},{"key":"5_CR25","first-page":"253","volume":"65","author":"M.A. Weiss","year":"1988","unstructured":"Weiss, M.A., Sedgewick, R., Hentschel, E., Pelin, A.: Shellsort and the Frobenius problem. Congr. Numer.\u00a065, 253\u2013260 (1988)","journal-title":"Congr. Numer."},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"562","DOI":"10.2307\/2320864","volume":"85","author":"H.S. Wilf","year":"1978","unstructured":"Wilf, H.S.: A circle-of-lights algorithm for the money-changing problem. Amer. Math. Monthly\u00a085, 562\u2013565 (1978)","journal-title":"Amer. Math. Monthly"},{"key":"5_CR27","unstructured":"Xu, Z., Shallit, J.: An NP-hardness result on the monoid Frobenius problem (preprint, 2008), \n                      http:\/\/arxiv.org\/abs\/0805.4049"},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S. Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci.\u00a0125, 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85780-8_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T22:08:58Z","timestamp":1675894138000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-85780-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540857792","9783540857808"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85780-8_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}