{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:23Z","timestamp":1759637903674},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662444641"},{"type":"electronic","value":"9783662444658"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44465-8_48","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:33:02Z","timestamp":1407839582000},"page":"565-576","source":"Crossref","is-referenced-by-count":2,"title":["Inferring Strings from Lyndon Factorization"],"prefix":"10.1007","author":[{"given":"Yuto","family":"Nakashima","sequence":"first","affiliation":[]},{"given":"Takashi","family":"Okabe","sequence":"additional","affiliation":[]},{"given":"Tomohiro","family":"I","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"48_CR1","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF01191471","volume":"28","author":"A. Apostolico","year":"1995","unstructured":"Apostolico, A., Crochemore, M.: Fast parallel Lyndon factorization with applications. Mathematical Systems Theory\u00a028(2), 89\u2013108 (1995)","journal-title":"Mathematical Systems Theory"},{"key":"48_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-45138-9_15","volume-title":"Mathematical Foundations of Computer Science 2003","author":"H. Bannai","year":"2003","unstructured":"Bannai, H., Inenaga, S., Shinohara, A., Takeda, M.: Inferring strings from graphs and arrays. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 208\u2013217. Springer, Heidelberg (2003)"},{"issue":"10","key":"48_CR3","doi-asserted-by":"publisher","first-page":"2239","DOI":"10.1016\/j.patcog.2008.11.010","volume":"42","author":"S. Brlek","year":"2009","unstructured":"Brlek, S., Lachaud, J.O., Proven\u00e7al, X., Reutenauer, C.: Lyndon + Christoffel = digitally convex. Pattern Recognition\u00a042(10), 2239\u20132246 (2009)","journal-title":"Pattern Recognition"},{"issue":"9","key":"48_CR4","first-page":"611","volume":"8","author":"M. Chemillier","year":"2004","unstructured":"Chemillier, M.: Periodic musical sequences and Lyndon words. Soft Comput.\u00a08(9), 611\u2013616 (2004)","journal-title":"Soft Comput."},{"issue":"1","key":"48_CR5","doi-asserted-by":"publisher","first-page":"81","DOI":"10.2307\/1970044","volume":"68","author":"K.T. Chen","year":"1958","unstructured":"Chen, K.T., Fox, R.H., Lyndon, R.C.: Free differential calculus. IV. the quotient groups of the lower central series. Annals of Mathematics\u00a068(1), 81\u201395 (1958)","journal-title":"Annals of Mathematics"},{"issue":"3","key":"48_CR6","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1145\/116825.116845","volume":"38","author":"M. Crochemore","year":"1991","unstructured":"Crochemore, M., Perrin, D.: Two-way string matching. J. ACM\u00a038(3), 651\u2013675 (1991)","journal-title":"J. ACM"},{"issue":"1","key":"48_CR7","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(94)90100-7","volume":"127","author":"J.W. Daykin","year":"1994","unstructured":"Daykin, J.W., Iliopoulos, C.S., Smyth, W.F.: Parallel RAM algorithms for factorizing words. Theor. Comput. Sci.\u00a0127(1), 53\u201367 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"16","key":"48_CR8","doi-asserted-by":"publisher","first-page":"2812","DOI":"10.1093\/bioinformatics\/bth335","volume":"20","author":"O. Delgrange","year":"2004","unstructured":"Delgrange, O., Rivals, E.: STAR: an algorithm to search for tandem approximate repeats. Bioinformatics\u00a020(16), 2812\u20132820 (2004)","journal-title":"Bioinformatics"},{"issue":"4","key":"48_CR9","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(83)90017-2","volume":"4","author":"J.P. Duval","year":"1983","unstructured":"Duval, J.P.: Factorizing words over an ordered alphabet. J. Algorithms\u00a04(4), 363\u2013381 (1983)","journal-title":"J. Algorithms"},{"key":"48_CR10","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(88)90113-2","volume":"60","author":"J.P. Duval","year":"1988","unstructured":"Duval, J.P.: G\u00e9n\u00e9ration d\u2019une section des classes de conjugaison et arbre des mots de Lyndon de longueur born\u00e9e. Theor. Comput. Sci.\u00a060, 255\u2013283 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"48_CR11","first-page":"51","volume":"10","author":"J.P. Duval","year":"2005","unstructured":"Duval, J.P., Lecroq, T., Lefebvre, A.: Border array on bounded alphabet. Journal of Automata, Languages and Combinatorics\u00a010(1), 51\u201360 (2005)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"issue":"2","key":"48_CR12","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1051\/ita:2008030","volume":"43","author":"J.P. Duval","year":"2009","unstructured":"Duval, J.P., Lecroq, T., Lefebvre, A.: Efficient validation and construction of border arrays and validation of string matching automata. RAIRO - Theoretical Informatics and Applications\u00a043(2), 281\u2013297 (2009)","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"key":"48_CR13","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1051\/ita:2002012","volume":"36","author":"J.P. Duval","year":"2002","unstructured":"Duval, J.P., Lefebvre, A.: Words over an ordered alphabet and suffix permutations. Theoretical Informatics and Applications\u00a036, 249\u2013259 (2002)","journal-title":"Theoretical Informatics and Applications"},{"key":"48_CR14","first-page":"223","volume":"42","author":"F. Franek","year":"2002","unstructured":"Franek, F., Gao, S., Lu, W., Ryan, P.J., Smyth, W.F., Sun, Y., Yang, L.: Verifying a border array in linear time. J. Comb. Math. and Comb. Comp.\u00a042, 223\u2013236 (2002)","journal-title":"J. Comb. Math. and Comb. Comp."},{"issue":"2","key":"48_CR15","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00224-013-9522-8","volume":"54","author":"P. Gawrychowski","year":"2014","unstructured":"Gawrychowski, P., Je\u017c, A., Je\u017c, \u0141.: Validating the Knuth-Morris-Pratt failure function, fast and online. Theory Comput. Syst.\u00a054(2), 337\u2013372 (2014)","journal-title":"Theory Comput. Syst."},{"unstructured":"Gil, J.Y., Scott, D.A.: A bijective string sorting transform. CoRR abs\/1201.3077 (2012)","key":"48_CR16"},{"key":"48_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/978-3-642-22300-6_41","volume-title":"Algorithms and Data Structures","author":"J. He","year":"2011","unstructured":"He, J., Liang, H., Yang, G.: Reversing longest previous factor tables is hard. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol.\u00a06844, pp. 488\u2013499. Springer, Heidelberg (2011)"},{"key":"48_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-16321-0_13","volume-title":"String Processing and Information Retrieval","author":"T. I","year":"2010","unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Counting and verifying maximal palindromes. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 135\u2013146. Springer, Heidelberg (2010)"},{"unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from suffix trees and links on a binary alphabet. In: Proc. PSC 2011, pp. 121\u2013130 (2011)","key":"48_CR19"},{"key":"48_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-642-38905-4_16","volume-title":"Combinatorial Pattern Matching","author":"T. I","year":"2013","unstructured":"I, T., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Efficient Lyndon factorization of grammar compressed text. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol.\u00a07922, pp. 153\u2013164. Springer, Heidelberg (2013)"},{"key":"48_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-319-02432-5_21","volume-title":"String Processing and Information Retrieval","author":"T. I","year":"2013","unstructured":"I, T., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Faster lyndon factorization algorithms for SLP and LZ78 compressed text. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol.\u00a08214, pp. 174\u2013185. Springer, Heidelberg (2013)"},{"unstructured":"Kufleitner, M.: On bijective variants of the Burrows-Wheeler transform. In: Proc. PSC 2009, pp. 65\u201379 (2009)","key":"48_CR22"},{"key":"48_CR23","first-page":"202","volume":"77","author":"R.C. Lyndon","year":"1954","unstructured":"Lyndon, R.C.: On Burnside\u2019s problem. Transactions of the American Mathematical Society\u00a077, 202\u2013215 (1954)","journal-title":"Transactions of the American Mathematical Society"},{"unstructured":"Matsubara, W., Ishino, A., Shinohara, A.: Inferring strings from runs. In: Proc. PSC 2010, pp. 150\u2013160 (2010)","key":"48_CR24"},{"issue":"1","key":"48_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00009247","volume":"23","author":"D. Moore","year":"1999","unstructured":"Moore, D., Smyth, W.F., Miller, D.: Counting distinct strings. Algorithmica\u00a023(1), 1\u201313 (1999)","journal-title":"Algorithmica"},{"issue":"2-3","key":"48_CR26","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.tcs.2008.01.011","volume":"395","author":"K.B. Sch\u00fcrmann","year":"2008","unstructured":"Sch\u00fcrmann, K.B., Stoye, J.: Counting suffix arrays and strings. Theoretical Computer Science\u00a0395(2-3), 220\u2013234 (2008)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44465-8_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T15:25:39Z","timestamp":1558970739000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44465-8_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662444641","9783662444658"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44465-8_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}