{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:36:31Z","timestamp":1755999391846},"publisher-location":"Berlin, Heidelberg","reference-count":55,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642223204"},{"type":"electronic","value":"9783642223211"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22321-1_1","type":"book-chapter","created":{"date-parts":[[2011,7,14]],"date-time":"2011-07-14T23:58:48Z","timestamp":1310687928000},"page":"1-14","source":"Crossref","is-referenced-by-count":3,"title":["Hunting Redundancies in Strings"],"prefix":"10.1007","author":[{"given":"Golnaz","family":"Badkobeh","sequence":"first","affiliation":[]},{"given":"Supaporn","family":"Chairungsee","sequence":"additional","affiliation":[]},{"given":"Maxime","family":"Crochemore","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Breslauer, D.: Of periods, quasiperiods, repetitions and covers, pp. 236\u2013248 (1997)","DOI":"10.1007\/3-540-63246-8_14"},{"issue":"3","key":"1_CR2","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(83)90109-3","volume":"22","author":"A. Apostolico","year":"1983","unstructured":"Apostolico, A., Preparata, F.P.: Optimal off-line detection of repetitions in a string. Theoret. Comput. Sci.\u00a022(3), 297\u2013315 (1983)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Badkobeh, G.: Fewest repetitions vs maximal-exponent powers in infinite binary words (2011) (submitted)","DOI":"10.1016\/j.tcs.2011.08.011"},{"key":"1_CR4","unstructured":"Badkobeh, G., Crochemore, M.: Bounded number of squares in infinite repetition-constrained binary words. In: Holub, J., Zd\u2019\u00e1rek, J. (eds.) Prague Stringology Conference, pp. 161\u2013166. Czech Technical University in Prague (2010) ISBN 978-80-01-04597-8"},{"key":"1_CR5","volume-title":"Text Compression","author":"T.C. Bell","year":"1990","unstructured":"Bell, T.C., Clearly, J.G., Witten, I.H.: Text Compression. Prentice Hall Inc., New Jersey (1990)"},{"key":"1_CR6","volume-title":"Algorithmic Aspects of Bioinformatics","author":"H.-J. B\u00f6ckenhauer","year":"2007","unstructured":"B\u00f6ckenhauer, H.-J., Bongartz, D.: Algorithmic Aspects of Bioinformatics. Springer, Berlin (2007)"},{"key":"1_CR7","first-page":"27","volume-title":"Seventh International Conference on Computer Science and Information Technologies (CSIT 2009)","author":"S. Chairungsee","year":"2009","unstructured":"Chairungsee, S., Crochemore, M.: Efficient computing of longest previous reverse factors. In: Shoukourian, Y. (ed.) Seventh International Conference on Computer Science and Information Technologies (CSIT 2009), pp. 27\u201330. The National Academy of Sciences of Armenia Publishers, Yerevan (2009)"},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-540-73437-6_31","volume-title":"Combinatorial Pattern Matching","author":"G. Chen","year":"2007","unstructured":"Chen, G., Puglisi, S.J., Smyth, W.F.: Fast and practical algorithms for computing all the runs in a string. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 307\u2013315. Springer, Heidelberg (2007)"},{"issue":"5","key":"1_CR9","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(81)90024-7","volume":"12","author":"M. Crochemore","year":"1981","unstructured":"Crochemore, M.: An optimal algorithm for computing the repetitions in a word. Inf. Process. Lett.\u00a012(5), 244\u2013250 (1981)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0304-3975(86)90041-1","volume":"45","author":"M. Crochemore","year":"1986","unstructured":"Crochemore, M.: Transducers and repetitions. Theoretical Computer Science\u00a045(1), 63\u201386 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"1_CR11","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1142\/S0129054110007416","volume":"21","author":"M. Crochemore","year":"2010","unstructured":"Crochemore, M., Fazekas, S.Z., Iliopoulos, C., Jayasekera, I.: Number of occurrences of powers in strings. International Journal of Foundations of Computer Science\u00a021(4), 535\u2013547 (2010)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"1_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"M. Crochemore","year":"2007","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press, Cambridge (2007)"},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-540-74456-6_42","volume-title":"Mathematical Foundations of Computer Science 2007","author":"M. Crochemore","year":"2007","unstructured":"Crochemore, M., Ilie, L.: Analysis of maximal repetitions in strings. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 465\u2013476. Springer, Heidelberg (2007)"},{"issue":"2","key":"1_CR14","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.ipl.2007.10.006","volume":"106","author":"M. Crochemore","year":"2008","unstructured":"Crochemore, M., Ilie, L.: Computing longest previous factors in linear time and applications. Information Processing Letters\u00a0106(2), 75\u201380 (2008), doi:10.1016\/j.ipl.2007.10.006","journal-title":"Information Processing Letters"},{"issue":"5","key":"1_CR15","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1016\/j.jcss.2007.09.003","volume":"74","author":"M. Crochemore","year":"2008","unstructured":"Crochemore, M., Ilie, L.: Maximal repetitions in strings. J. Comput. Syst. Sci.\u00a074(5), 796\u2013807 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-10217-2_18","volume-title":"Combinatorial Algorithms","author":"M. Crochemore","year":"2009","unstructured":"Crochemore, M., Ilie, L., Iliopoulos, C., Kubica, M., Rytter, W., Wale\u0144, T.: LPF computation revisited. In: Fiala, J., Kratochv\u00edl, J., Miller, M. (eds.) IWOCA 2009. LNCS, vol.\u00a05874, pp. 158\u2013169. Springer, Heidelberg (2009)"},{"key":"1_CR17","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1109\/DCC.2008.36","volume-title":"18th Data Compression Conference","author":"M. Crochemore","year":"2008","unstructured":"Crochemore, M., Ilie, L., Smyth, W.F.: A simple algorithm for computing the Lempel-Ziv factorization. In: Storer, J.A., Marcellin, M.W. (eds.) 18th Data Compression Conference, March 25-27, pp. 482\u2013488. IEEE Computer Society, Los Alamitos (2008)"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Ilie, L., Tinta, L.: The \u201druns\u201d conjecture. In: de Felice, C., Carpi, A. (eds.) Theoretical Computer Science (2010) (in press, corrected proof )","DOI":"10.1016\/j.tcs.2010.06.019"},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/978-3-642-11266-9_25","volume-title":"SOFSEM 2010: Theory and Practice of Computer Science","author":"M. Crochemore","year":"2010","unstructured":"Crochemore, M., Iliopoulos, C., Kubica, M., Rytter, W., Wale\u0144, T.: Efficient algorithms for two extensions of LPF table: The power of suffix arrays. In: van Leeuwen, J., Muscholl, A., Peleg, D., Pokorn\u00fd, J., Rumpe, B. (eds.) SOFSEM 2010. LNCS, vol.\u00a05901, pp. 296\u2013307. Springer, Heidelberg (2010)"},{"issue":"5","key":"1_CR20","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/BF01190846","volume":"13","author":"M. Crochemore","year":"1995","unstructured":"Crochemore, M., Rytter, W.: Squares, cubes and time-space efficient string-searching. Algorithmica\u00a013(5), 405\u2013425 (1995)","journal-title":"Algorithmica"},{"issue":"1","key":"1_CR21","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/0097-3165(72)90011-8","volume":"13","author":"F. Dejean","year":"1972","unstructured":"Dejean, F.: Sur un th\u00e9or\u00e8me de Thue. J. Comb. Theory, Ser. A\u00a013(1), 90\u201399 (1972)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"3","key":"1_CR22","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/0097-3165(76)90023-6","volume":"20","author":"F.M. Dekking","year":"1976","unstructured":"Dekking, F.M.: On repetitions of blocks in binary sequences. J. Comb. Theory, Ser. A\u00a020(3), 292\u2013299 (1976)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Fraenkel, A.S., Simpson, J.: How many squares must a binary sequence contain? Electr. J. Comb.\u00a02 (1995)","DOI":"10.37236\/1196"},{"issue":"1","key":"1_CR24","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1006\/jcta.1997.2843","volume":"82","author":"A.S. Fraenkel","year":"1998","unstructured":"Fraenkel, A.S., Simpson, J.: How many squares can a string contain? J. Comb. Theory, Ser. A\u00a082(1), 112\u2013120 (1998)","journal-title":"Comb. Theory, Ser. A"},{"issue":"4","key":"1_CR25","first-page":"579","volume":"8","author":"F. Franek","year":"2003","unstructured":"Franek, F., Smyth, W.F., Tang, Y.: Computing all repeats using suffix arrays. Journal of Automata, Languages and Combinatorics\u00a08(4), 579\u2013591 (2003)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"1_CR26","unstructured":"Franek, F., Yang, Q.: An asymptotic lower bound for the maximal-number-of-runs function. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference. Department of Computer Science and Engineering, Faculty of Electrical Engineering, pp. 3\u20138. Czech Technical University (2006)"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Giraud, M.: Not so many runs in strings. In: Martin-Vide, C. (ed.) 2nd International Conference on Language and Automata Theory and Applications (2008)","DOI":"10.1007\/978-3-540-88282-4_22"},{"issue":"4","key":"1_CR28","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.jcss.2004.03.004","volume":"69","author":"D. Gusfield","year":"2004","unstructured":"Gusfield, D., Stoye, J.: Linear time algorithms for finding and representing all the tandem repeats in a string. J. Comput. Syst. Sci.\u00a069(4), 525\u2013546 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR29","first-page":"164","volume":"89","author":"T. Harju","year":"2006","unstructured":"Harju, T., Nowotka, D.: Binary words with few squares. Bulletin of the EATCS\u00a089, 164\u2013166 (2006)","journal-title":"Bulletin of the EATCS"},{"issue":"1","key":"1_CR30","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.jcta.2005.01.006","volume":"112","author":"L. Ilie","year":"2005","unstructured":"Ilie, L.: A simple proof that a word of length has at most 2 distinct squares. J. Comb. Theory, Ser. A\u00a0112(1), 163\u2013164 (2005)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"3","key":"1_CR31","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/j.tcs.2007.03.025","volume":"380","author":"L. Ilie","year":"2007","unstructured":"Ilie, L.: A note on the number of squares in a word. Theor. Comput. Sci.\u00a0380(3), 373\u2013376 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1-2","key":"1_CR32","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0304-3975(96)00141-7","volume":"172","author":"C.S. Iliopoulos","year":"1997","unstructured":"Iliopoulos, C.S., Moore, D., Smyth, W.F.: A characterization of the squares in a Fibonacci string. Theoret. Comput. Sci.\u00a0172(1-2), 281\u2013291 (1997)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1_CR33","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcta.2003.12.004","volume":"105","author":"J. Karhum\u00e4ki","year":"2004","unstructured":"Karhum\u00e4ki, J., Shallit, J.: Polynomial versus exponential growth in repetition-free binary words. J. Comb. Theory, Ser. A\u00a0105(2), 335\u2013347 (2004)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"1_CR34","first-page":"596","volume-title":"Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science","author":"R. Kolpakov","year":"1999","unstructured":"Kolpakov, R., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, pp. 596\u2013604. IEEE Computer Society Press, New York (1999)"},{"key":"1_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-540-69068-9_5","volume-title":"Combinatorial Pattern Matching","author":"R. Kolpakov","year":"2008","unstructured":"Kolpakov, R., Kucherov, G.: Searching for gapped palindromes. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 18\u201330. Springer, Heidelberg (2008)"},{"key":"1_CR36","volume-title":"Combinatorics on Words","year":"1997","unstructured":"Lothaire, M. (ed.): Combinatorics on Words, 2nd edn. Cambridge University Press, Cambridge (1997)","edition":"2"},{"volume-title":"Algebraic Combinatorics on Words","year":"2001","key":"1_CR37","unstructured":"Lothaire, M. (ed.): Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2001)"},{"volume-title":"Appplied Combinatorics on Words","year":"2005","key":"1_CR38","unstructured":"Lothaire, M. (ed.): Appplied Combinatorics on Words. Cambridge University Press, Cambridge (2005)"},{"issue":"6","key":"1_CR39","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1016\/0092-8674(93)90585-E","volume":"72","author":"M. MacDonald","year":"1993","unstructured":"MacDonald, M., Ambrose, C.M.: A novel gene containing a trinucleotide repeat that is expanded and unstable on huntington\u2019s disease chromosomes. Cell\u00a072(6), 971\u2013983 (1993)","journal-title":"Cell"},{"key":"1_CR40","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0166-218X(89)90051-6","volume":"25","author":"M.G. Main","year":"1989","unstructured":"Main, M.G.: Detecting leftmost maximal periodicities. Discret. Appl. Math.\u00a025, 145\u2013153 (1989)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"1_CR41","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"M.G. Main","year":"1984","unstructured":"Main, M.G., Lorentz, R.J.: An O(n logn) algorithm for finding all repetitions in a string. J. Algorithms\u00a05(3), 422\u2013432 (1984)","journal-title":"J. Algorithms"},{"key":"1_CR42","unstructured":"Matsubara, W., Kusano, K., Ishino, A., Bannai, H., Shinohara, A.: New lower bounds for the maximum number of runs in a string. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference. Prague Stringology Club, Department of Computer Science and Engineering, Faculty of Electrical Engineering, pp.140\u2013145. Czech Technical University in Prague (2008)"},{"issue":"3","key":"1_CR43","first-page":"427","volume":"40","author":"P. Ochem","year":"2006","unstructured":"Ochem, P.: A generator of morphisms for infinite words. ITA\u00a040(3), 427\u2013441 (2006)","journal-title":"ITA"},{"issue":"2","key":"1_CR44","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/0020-0190(81)90004-1","volume":"12","author":"J.J. Pansiot","year":"1981","unstructured":"Pansiot, J.J.: The morse sequence and iterated morphisms. Inf. Process. Lett.\u00a012(2), 68\u201370 (1981)","journal-title":"Inf. Process. Lett."},{"issue":"1-3","key":"1_CR45","first-page":"165","volume":"401","author":"S.J. Puglisi","year":"2008","unstructured":"Puglisi, S.J., Simpson, J., Smyth, W.F.: How many runs can a string contain? Theor. Comput. Sci.\u00a0401(1-3), 165\u2013171 (2008)","journal-title":"Comput. Sci."},{"issue":"1","key":"1_CR46","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.tcs.2005.01.005","volume":"339","author":"N. Rampersad","year":"2005","unstructured":"Rampersad, N., Shallit, J., Wei Wang, M.: Avoiding large squares in infinite binary words. Theor. Comput. Sci.\u00a0339(1), 19\u201334 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR47","unstructured":"Rao, M.: Last cases of Dejean\u2019s conjecture. In: Carpi, A., de Felice, C. (eds.) WORDS 2009. University of Salerno, Italy (2009)"},{"key":"1_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/11672142_14","volume-title":"STACS 2006","author":"W. Rytter","year":"2006","unstructured":"Rytter, W.: The number of runs in a string: Improved analysis of the linear upper bound. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 184\u2013195. Springer, Heidelberg (2006)"},{"issue":"9","key":"1_CR49","doi-asserted-by":"publisher","first-page":"1459","DOI":"10.1016\/j.ic.2007.01.007","volume":"205","author":"W. Rytter","year":"2007","unstructured":"Rytter, W.: The number of runs in a string. Inf. Comput.\u00a0205(9), 1459\u20131469 (2007)","journal-title":"Inf. Comput."},{"key":"1_CR50","doi-asserted-by":"crossref","unstructured":"S\u00e9\u00e9bold, P.: Sur les morphismes qui engendrent des mots infinis ayant des facteurs prescrits, pp. 301\u2013311 (1983)","DOI":"10.1007\/BFb0036490"},{"key":"1_CR51","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1142\/S0129054104002443","volume":"15","author":"J. Shallit","year":"2004","unstructured":"Shallit, J.: Simultaneous avoidance of large squares and fractional powers in infinite binary words. Intl. J. Found. Comput. Sci.\u00a015, 317\u2013327 (2004)","journal-title":"Intl. J. Found. Comput. Sci."},{"key":"1_CR52","first-page":"129","volume":"46","author":"J. Simpson","year":"2010","unstructured":"Simpson, J.: Modified Padovan words and the maximum number of runs in a word. Australasian J. of Comb.\u00a046, 129\u2013145 (2010)","journal-title":"Australasian J. of Comb."},{"key":"1_CR53","first-page":"1","volume":"7","author":"Thue","year":"1906","unstructured":"Thue: Uber unendliche zeichenreihen. Norske vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana\u00a07, 1\u201322 (1906)","journal-title":"Norske vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana"},{"key":"1_CR54","unstructured":"Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes. Van Nostrand Reinhold (1994)"},{"key":"1_CR55","doi-asserted-by":"crossref","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 337\u2013343 (1977)","DOI":"10.1109\/TIT.1977.1055714"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22321-1_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T05:26:12Z","timestamp":1592717172000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22321-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642223204","9783642223211"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22321-1_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}