{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T05:47:35Z","timestamp":1761630455486},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540439967"},{"type":"electronic","value":"9783540456551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45655-4_35","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T11:37:01Z","timestamp":1179747421000},"page":"320-329","source":"Crossref","is-referenced-by-count":6,"title":["Repetition Complexity of Words"],"prefix":"10.1007","author":[{"given":"Lucian","family":"Ilie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheng","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaizhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,8,29]]},"reference":[{"key":"35_CR1","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., and Preparata, F., Optimal off-line detection of repetitions in a string, Theoret. Comput. Sci. 22 (1983) 297\u2013315.","journal-title":"Theoret. Comput. Sci."},{"key":"35_CR2","first-page":"758","volume":"49","author":"N.G. Bruijn de","year":"1946","unstructured":"de Bruijn, N.G., A combinatorial problem, Proc. Kon. Ned. Akad. Wetensch. 49 (1946) 758\u2013764.","journal-title":"Proc. Kon. Ned. Akad. Wetensch."},{"key":"35_CR3","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1145\/321832.321839","volume":"21","author":"G.J. Chaitin","year":"1974","unstructured":"Chaitin, G.J, Information-theoretic limitations of formal systems, J. Assoc. Comput. Mach. 21 (1974) 403\u2013424.","journal-title":"J. Assoc. Comput. Mach."},{"key":"35_CR4","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/978-3-642-59136-5_6","volume-title":"Handbook of Formal Languages","author":"C. Choffrut","year":"1997","unstructured":"Choffrut, C., and Karhum\u00e4ki, J., Combinatorics of Words, in: G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages, Vol. I, Springer-Verlag, Berlin, 1997, 329\u2013438."},{"key":"35_CR5","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/BF01762232","volume":"7","author":"E.M. Coven","year":"1973","unstructured":"Coven, E.M., and Hedlund, G., Sequences with minimal block growth, Math. Sytems Theory 7 (1973) 138\u2013153.","journal-title":"Math. Sytems Theory"},{"issue":"5","key":"35_CR6","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, Inform. Proc. Lett. 12(5) (1981) 244\u2013250.","journal-title":"Inform. Proc. Lett."},{"key":"35_CR7","unstructured":"Crochemore, M., and Rytter, W., Text Algorithms, Oxford Univ. Press, 1994."},{"key":"35_CR8","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/BF01190846","volume":"13","author":"M. Crochemore","year":"1995","unstructured":"Crochemore, M., and Rytter, W., Squares, cubes, and time-space efficient string matching, Algorithmica 13 (1995) 405\u2013425. Oxford Univ. Press, 1994.","journal-title":"Algorithmica"},{"key":"35_CR9","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. Combin. Theory, Ser. A 13 (1972) 90\u201399.","journal-title":"J. Combin. Theory, Ser. A"},{"key":"35_CR10","volume-title":"Computers and Intractability. A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S., Computers and Intractability. A Guide to the Theory of NP-completeness, W.H. Freeman and Co., San Francisco, 1979."},{"key":"35_CR11","series-title":"Lect Notes Comput Sci","first-page":"515","volume-title":"Proc. of STACSrs92","author":"G. Hansel","year":"1992","unstructured":"Hansel, G., Perrin, D., and Simon, I., Compression and entropy, Proc. of STACSrs92, LNCS 577, Springer-Verlag, 1992, 515\u2013528."},{"key":"35_CR12","first-page":"1","volume":"1","author":"A.N. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N., Three approaches to the quantitative definition of information, Probl. Inform. Transmission 1 (1965) 1\u20137.","journal-title":"Probl. Inform. Transmission"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Kolpakov, R., and Kucherov, G., Finding maximal repetitions in a word in linear time, Proc. of FOCS\u201999, 596\u2013604.","DOI":"10.1109\/SFFCS.1999.814634"},{"issue":"1","key":"35_CR14","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A. Lempel","year":"1976","unstructured":"Lempel, A., and Ziv, J., On the complexity of finite sequences IEEE Trans. Information Theory 22(1) (1976) 75\u201381.","journal-title":"IEEE Trans. Information Theory"},{"key":"35_CR15","volume-title":"Combinatorics on Words","author":"M. Lothaire","year":"1983","unstructured":"Lothaire, M., Combinatorics on Words, Addison-Wesley, Reading, MA, 1983."},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"Lothaire, M., Algebraic Combinatorics on Words, Cambridge Univ. Press, 2002.","DOI":"10.1017\/CBO9781107326019"},{"key":"35_CR17","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"M. Main","year":"1984","unstructured":"Main, M., and Lorentz, R., An O(nlgn) algorithm for finding all repetitions in a string, J. Algorithms 5 (1984) 422\u2013432.","journal-title":"J. Algorithms"},{"key":"35_CR18","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0166-218X(89)90051-6","volume":"25","author":"M. Main","year":"1989","unstructured":"Main, M., Detecting leftmost maximal periodicities, Discrete Appl. Math. 25 (1989) 145\u2013153.","journal-title":"Discrete Appl. Math."},{"key":"35_CR19","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P., The definition of random sequences, Inform. and Control 9 (1966) 602\u2013619.","journal-title":"Inform. and Control"},{"key":"35_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1215\/S0012-7094-44-01101-4","volume":"11","author":"M. Morse","year":"1944","unstructured":"Morse, M., and Hedlund, G., Unending chess, symbolic dynamics and a problem in semigroups, Duke Math. J. 11 (1944) 1\u20137.","journal-title":"Duke Math. J."},{"key":"35_CR21","doi-asserted-by":"crossref","unstructured":"Storer, J.A., Szymanski, T.G., The macro model for data compression, Proc. of 10th STOC, 1978, 30\u201339.","DOI":"10.1145\/800133.804329"},{"key":"35_CR22","first-page":"1","volume":"7","author":"A. Thue","year":"1906","unstructured":"Thue, A., Uber unendliche Zeichenreihen, Norske Vid. Selsk. Skr. Mat.-Nat. Kl. (Kristiania) 7 (1906) 1\u201322.","journal-title":"Norske Vid. Selsk. Skr. Mat.-Nat. Kl. (Kristiania)"},{"key":"35_CR23","first-page":"1","volume":"5","author":"A. Thue","year":"1912","unstructured":"Thue, A., Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. Mat.-Nat. Kl. (Kristiania) 5 (1912) 1\u201367.","journal-title":"Norske Vid. Selsk. Skr. Mat.-Nat. Kl. (Kristiania)"},{"issue":"3","key":"35_CR24","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., and Lempel, A., A universal algorithm for sequential data compression, IEEE Trans. Information Theory 23(3) (1977) 337\u2013343.","journal-title":"IEEE Trans. Information Theory"},{"issue":"5","key":"35_CR25","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., and Lempel, A., Compression of individual sequences via variable length encoding, IEEE Trans. Information Theory 24(5) (1978) 530\u2013536.","journal-title":"IEEE Trans. Information Theory"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45655-4_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T06:27:14Z","timestamp":1556432834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45655-4_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540439967","9783540456551"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-45655-4_35","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}