{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:16:34Z","timestamp":1742912194879,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030895426"},{"type":"electronic","value":"9783030895433"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-89543-3_16","type":"book-chapter","created":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T02:03:25Z","timestamp":1634781805000},"page":"189-200","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Most Pseudo-copy Languages Are Not Context-Free"],"prefix":"10.1007","author":[{"given":"Hyunjoon","family":"Cheon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joonghyuk","family":"Hahn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sang-Ki","family":"Ko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,20]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Anderson, T., Rampersad, N., Santean, N., Shallit, J.: Finite automata, palindromes, powers, and patterns. In: Proceedings of the 2nd International Conference on Language and Automata Theory and Applications, pp. 52\u201363 (2008)","DOI":"10.1007\/978-3-540-88282-4_7"},{"issue":"3","key":"16_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.: Optimal off-line detection of repetitions in a string. Theor. Comput. Sci. 22(3), 297\u2013315 (1983)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"16_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s11047-020-09797-0","volume":"20","author":"H Bordihn","year":"2020","unstructured":"Bordihn, H., Mitrana, V., P\u0103un, A., P\u0103un, M.: Hairpin completions and reductions: semilinearity properties. Nat. Comput. 20(2), 193\u2013203 (2020). https:\/\/doi.org\/10.1007\/s11047-020-09797-0","journal-title":"Nat. Comput."},{"key":"16_CR4","unstructured":"Bordihn, H., Shallit, J.: Personal communication"},{"key":"16_CR5","unstructured":"Crochemore, M.: Recherche lin\u00e9aire d\u2019un carr\u00e9 dans un mot. Comptes rendus de l\u2019Acad\u00e9mie des sciences. S\u00e9rie I, Math\u00e9matique 296(18), 781\u2013784 (1983)"},{"issue":"1","key":"16_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1051\/ita\/1983170100131","volume":"17","author":"A Ehrenfeucht","year":"1983","unstructured":"Ehrenfeucht, A., Rozenberg, G.: On the separating power of EOL systems. RAIRO Theor. Inform. Appl. 17(1), 13\u201322 (1983)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"16_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, USA (1997)"},{"issue":"2","key":"16_CR8","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1002\/j.1538-7305.1950.tb00463.x","volume":"29","author":"RW Hamming","year":"1950","unstructured":"Hamming, R.W.: Error detecting and error correcting codes. Bell Syst. Tech. J. 29(2), 147\u2013160 (1950)","journal-title":"Bell Syst. Tech. J."},{"key":"16_CR9","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"2006","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Pearson Education Inc, Boston, MA, USA (2006)","edition":"3"},{"issue":"1","key":"16_CR10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(02)00448-6","volume":"303","author":"R Kolpakov","year":"2003","unstructured":"Kolpakov, R., Kucherov, G.: Finding approximate repetitions under Hamming distance. Theor. Comput. Sci. 303(1), 135\u2013156 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR11","series-title":"Emergence, Complexity and Computation","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-319-73216-9_19","volume-title":"Reversibility and Universality","author":"M Kutrib","year":"2018","unstructured":"Kutrib, M., Malcher, A., Wendlandt, M.: Queue automata: foundations and\u00a0developments. In: Adamatzky, A. (ed.) Reversibility and Universality. ECC, vol. 30, pp. 385\u2013431. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-73216-9_19"},{"issue":"1","key":"16_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/106652701300099038","volume":"8","author":"GM Landau","year":"2001","unstructured":"Landau, G.M., Schmidt, J.P., Sokol, D.: An algorithm for approximate tandem repeats. J. Comput. Biol. 8(1), 1\u201318 (2001)","journal-title":"J. Comput. Biol."},{"issue":"8","key":"16_CR13","first-page":"707","volume":"10","author":"VI Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Doklady 10(8), 707\u2013710 (1966)","journal-title":"Sov. Phys. Doklady"},{"issue":"3","key":"16_CR14","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1002\/malq.200410032","volume":"51","author":"G Lischke","year":"2005","unstructured":"Lischke, G.: Squares of regular languages. Math. Log. Q. 51(3), 299\u2013304 (2005)","journal-title":"Math. Log. Q."},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Lothaire, M.: Combinatorics on Words, 2nd ed. Cambridge University Press, Cambridge (1997)","DOI":"10.1017\/CBO9780511566097"},{"issue":"3","key":"16_CR16","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"MG Main","year":"1984","unstructured":"Main, M.G., Lorentz, R.J.: An $${O}(n \\log n)$$ algorithm for finding all repetitions in a string. J. Algorithms 5(3), 422\u2013432 (1984)","journal-title":"J. Algorithms"},{"issue":"2","key":"16_CR17","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0214031","volume":"14","author":"WF Ogden","year":"1985","unstructured":"Ogden, W.F., Ross, R.J., Winklmann, K.: An \u201cinterchange lemma\u2019\u2019 for context-free languages. SIAM J. Comput. 14(2), 410\u2013415 (1985)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"16_CR18","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1051\/ita\/1982160301911","volume":"16","author":"RJ Ross","year":"1982","unstructured":"Ross, R.J., Winklmann, K.: Repetitive strings are not context-free. RAIRO Theor. Inform. Appl. 16(3), 191\u2013199 (1982)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"16_CR19","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"2013","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 3rd edn. Cengage Learning, Boston, MA, USA (2013)","edition":"3"},{"issue":"1","key":"16_CR20","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1016\/S0304-3975(01)00121-9","volume":"270","author":"J Stoye","year":"2002","unstructured":"Stoye, J., Gusfield, D.: Simple and flexible detection of contiguous repeats using a suffix tree. Theor. Comput. Sci. 270(1), 843\u2013856 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"16_CR21","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF02234250","volume":"5","author":"R Vollmar","year":"1970","unstructured":"Vollmar, R.: \u00dcber einen automaten mit pufferspeicherung. Computing 5(1), 57\u201370 (1970)","journal-title":"Computing"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-89543-3_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T02:08:14Z","timestamp":1634782094000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-89543-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030895426","9783030895433"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-89543-3_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 October 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tainan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 October 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 October 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon-conference.org\/2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"131","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"56","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}