{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T11:12:07Z","timestamp":1743073927619,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030866914"},{"type":"electronic","value":"9783030866921"}],"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-86692-1_7","type":"book-chapter","created":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T21:24:41Z","timestamp":1632777881000},"page":"68-82","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["String Covers of a Tree"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0067-6401","authenticated-orcid":false,"given":"Jakub","family":"Radoszewski","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9162-6724","authenticated-orcid":false,"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2207-0053","authenticated-orcid":false,"given":"Juliusz","family":"Straszy\u0144ski","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7369-3309","authenticated-orcid":false,"given":"Tomasz","family":"Wale\u0144","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1988-3507","authenticated-orcid":false,"given":"Wiktor","family":"Zuba","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,27]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.dam.2015.05.019","volume":"212","author":"A Alatabbi","year":"2016","unstructured":"Alatabbi, A., Rahman, M.S., Smyth, W.F.: Computing covers using prefix tables. Discret. Appl. Math. 212, 2\u20139 (2016). https:\/\/doi.org\/10.1016\/j.dam.2015.05.019","journal-title":"Discret. Appl. Math."},{"key":"7_CR2","doi-asserted-by":"publisher","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: 39th Annual Symposium on Foundations of Computer Science, FOCS \u201998, pp. 534\u2013544. IEEE Computer Society, Palo Alto, California, USA (1998). https:\/\/doi.org\/10.1109\/SFCS.1998.743504","DOI":"10.1109\/SFCS.1998.743504"},{"key":"7_CR3","unstructured":"Antoniou, P., Crochemore, M., Iliopoulos, C.S., Jayasekera, I., Landau, G.M.: Conservative string covering of indeterminate strings. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference 2008, Prague, Czech Republic, 1\u20133 September 2008, pp. 108\u2013115. Prague Stringology Club, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague (2008). http:\/\/www.stringology.org\/event\/2008\/p10.html"},{"issue":"1","key":"7_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0020-0190(91)90056-N","volume":"39","author":"A Apostolico","year":"1991","unstructured":"Apostolico, A., Farach, M., Iliopoulos, C.S.: Optimal superprimitivity testing for strings. Inf. Process. Lett. 39(1), 17\u201320 (1991). https:\/\/doi.org\/10.1016\/0020-0190(91)90056-N","journal-title":"Inf. Process. Lett."},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"104462","DOI":"10.1016\/j.ic.2019.104462","volume":"270","author":"C Barton","year":"2020","unstructured":"Barton, C., Kociumaka, T., Liu, C., Pissis, S.P., Radoszewski, J.: Indexing weighted sequences: neat and efficient. Inf. Comput. 270, 104462 (2020). https:\/\/doi.org\/10.1016\/j.ic.2019.104462","journal-title":"Inf. Comput."},{"key":"7_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/3-540-45995-2_44","volume-title":"LATIN 2002: Theoretical Informatics","author":"MA Bender","year":"2002","unstructured":"Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 508\u2013515. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45995-2_44"},{"issue":"6","key":"7_CR7","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90111-8","volume":"44","author":"D Breslauer","year":"1992","unstructured":"Breslauer, D.: An on-line string superprimitivity test. Inf. Process. Lett. 44(6), 345\u2013347 (1992). https:\/\/doi.org\/10.1016\/0020-0190(92)90111-8","journal-title":"Inf. Process. Lett."},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-319-21500-6_12","volume-title":"Developments in Language Theory","author":"S Brlek","year":"2015","unstructured":"Brlek, S., Lafreni\u00e8re, N., Proven\u00e7al, X.: Palindromic complexity of trees. In: Potapov, I. (ed.) DLT 2015. LNCS, vol. 9168, pp. 155\u2013166. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21500-6_12"},{"key":"7_CR9","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Radoszewski, J., Rytter, W., Wale\u0144, T., Zuba, W.: Computing covers of 2D-strings. In: Gawrychowski, P., Starikovskaya, T. (eds.) 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, 5\u20137 July 2021, Wroc\u0142aw, Poland. LIPIcs, vol. 191, pp. 12:1\u201312:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2021.12","DOI":"10.4230\/LIPIcs.CPM.2021.12"},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-642-31265-6_3","volume-title":"Combinatorial Pattern Matching","author":"M Crochemore","year":"2012","unstructured":"Crochemore, M., et al.: The maximum number of squares in a tree. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol. 7354, pp. 27\u201340. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31265-6_3"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2017.05.026","volume":"698","author":"M Crochemore","year":"2017","unstructured":"Crochemore, M., Iliopoulos, C.S., Kociumaka, T., Radoszewski, J., Rytter, W., Wale\u0144, T.: Covering problems for partial words and for indeterminate strings. Theor. Comput. Sci. 698, 25\u201339 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2017.05.026","journal-title":"Theor. Comput. Sci."},{"key":"7_CR12","unstructured":"Funakoshi, M., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Computing maximal palindromes and distinct palindromes in a trie. In: Holub, J., Zd\u00e1rek, J. (eds.) Prague Stringology Conference 2019, Prague, Czech Republic, 26\u201328 August 2019, pp. 3\u201315. Czech Technical University in Prague, Faculty of Information Technology, Department of Theoretical Computer Science (2019). http:\/\/www.stringology.org\/event\/2019\/p02.html"},{"key":"7_CR13","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Kociumaka, T., Rytter, W., Wale\u0144, T.: Tight bound for the number of distinct palindromes in a tree. In: Iliopoulos, C.S, Puglisi, S., Yilmaz, E. (eds.) SPIRE 2015. LNCS, vol. 9309, pp. 270\u2013276. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-23826-5_26","DOI":"10.1007\/978-3-319-23826-5_26"},{"key":"7_CR14","unstructured":"Gawrychowski, P., Kociumaka, T., Rytter, W., Wale\u0144, T.: Tight bound for the number of distinct palindromes in a tree. CoRR abs\/2008.13209 (2020). arXiv:2008.13209"},{"key":"7_CR15","unstructured":"Harary, F.: Graph Theory. Reading, Addison-Wesley, Boston, MA (1994)"},{"issue":"1","key":"7_CR16","first-page":"40","volume":"10","author":"CS Iliopoulos","year":"2003","unstructured":"Iliopoulos, C.S., Mohamed, M., Mouchard, L., Perdikuri, K., Smyth, W.F., Tsakalidis, A.K.: String regularities with don\u2019t cares. Nordic J. Comput. 10(1), 40\u201351 (2003)","journal-title":"Nordic J. Comput."},{"key":"7_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-030-59212-7_10","volume-title":"String Processing and Information Retrieval","author":"N Kikuchi","year":"2020","unstructured":"Kikuchi, N., Hendrian, D., Yoshinaka, R., Shinohara, A.: Computing covers under substring consistent equivalence relations. In: Boucher, C., Thankachan, S.V. (eds.) SPIRE 2020. LNCS, vol. 12303, pp. 131\u2013146. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-59212-7_10"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2014.04.015","volume":"544","author":"T Kociumaka","year":"2014","unstructured":"Kociumaka, T., Pachocki, J., Radoszewski, J., Rytter, W., Wale\u0144, T.: Efficient counting of square substrings in a tree. Theor. Comput. Sci. 544, 60\u201373 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2014.04.015","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"7_CR19","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1007\/s00453-016-0271-3","volume":"79","author":"T Kociumaka","year":"2017","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., Wale\u0144, T.: String powers in trees. Algorithmica 79(3), 814\u2013834 (2017). https:\/\/doi.org\/10.1007\/s00453-016-0271-3","journal-title":"Algorithmica"},{"key":"7_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-319-32859-1_27","volume-title":"Mathematical Aspects of Computer and Information Sciences","author":"T Kociumaka","year":"2016","unstructured":"Kociumaka, T., Radoszewski, J., Wi\u015bniewski, B.: Subquadratic-time algorithms for abelian stringology problems. In: Kotsireas, I.S., Rump, S.M., Yap, C.K. (eds.) MACIS 2015. LNCS, vol. 9582, pp. 320\u2013334. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-32859-1_27"},{"issue":"3","key":"7_CR21","doi-asserted-by":"publisher","first-page":"332","DOI":"10.3934\/ms.2017.3.332","volume":"4","author":"T Kociumaka","year":"2017","unstructured":"Kociumaka, T., Radoszewski, J., Wi\u015bniewski, B.: Subquadratic-time algorithms for abelian stringology problems. AIMS Med. Sci. 4(3), 332\u2013351 (2017). https:\/\/doi.org\/10.3934\/ms.2017.3.332","journal-title":"AIMS Med. Sci."},{"key":"7_CR22","doi-asserted-by":"publisher","unstructured":"Kosaraju, S.R.: Efficient tree pattern matching (preliminary version). In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October\u20131 November 1989, pp. 178\u2013183. IEEE Computer Society (1989). https:\/\/doi.org\/10.1109\/SFCS.1989.63475","DOI":"10.1109\/SFCS.1989.63475"},{"key":"7_CR23","unstructured":"Matsuda, S., Inenaga, S., Bannai, H., Takeda, M.: Computing abelian covers and abelian runs. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference 2014, Prague, Czech Republic, 1\u20133 September 2014, pp. 43\u201351. Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague (2014). http:\/\/www.stringology.org\/event\/2014\/p05.html"},{"issue":"5","key":"7_CR24","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0020-0190(94)00045-X","volume":"50","author":"DWG Moore","year":"1994","unstructured":"Moore, D.W.G., Smyth, W.F.: An optimal algorithm to compute all the covers of a string. Inf. Process. Lett. 50(5), 239\u2013246 (1994). https:\/\/doi.org\/10.1016\/0020-0190(94)00045-X","journal-title":"Inf. Process. Lett."},{"key":"7_CR25","doi-asserted-by":"publisher","unstructured":"Moore, D.W.G., Smyth, W.F.: A correction to \u201cAn optimal algorithm to compute all the covers of a string\". Inf. Process. Lett. 54(2), 101\u2013103 (1995). https:\/\/doi.org\/10.1016\/0020-0190(94)00235-Q","DOI":"10.1016\/0020-0190(94)00235-Q"},{"key":"7_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-030-14812-6_33","volume-title":"Theory and Applications of Models of Computation","author":"A Popa","year":"2019","unstructured":"Popa, A., Tanasescu, A.: An output-sensitive algorithm for the minimization of 2-dimensional string covers. In: Gopal, T.V., Watada, J. (eds.) TAMC 2019. LNCS, vol. 11436, pp. 536\u2013549. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-14812-6_33"},{"key":"7_CR27","doi-asserted-by":"publisher","unstructured":"Radoszewski, J., Straszy\u0144ski, J.: Efficient computation of 2-covers of a string. In: Grandoni, F., Herman, G., Sanders, P. (eds.) 28th Annual European Symposium on Algorithms, ESA 2020, 7\u20139 September 2020, Pisa, Italy (Virtual Conference). LIPIcs, vol. 173, pp. 77:1\u201377:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.77","DOI":"10.4230\/LIPIcs.ESA.2020.77"},{"key":"7_CR28","first-page":"1061","volume":"E86\u2013A(5)","author":"T Shibuya","year":"2003","unstructured":"Shibuya, T.: Constructing the suffix tree of a tree with a large alphabet. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E86\u2013A(5), 1061\u20131066 (2003)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"7_CR29","doi-asserted-by":"publisher","unstructured":"Sugahara, R., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Computing runs on a trie. In: Pisanti, N., Pissis, S.P. (eds.) 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, June 18\u201320, 2019, Pisa, Italy. LIPIcs, vol. 128, pp. 23:1\u201323:11. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2019.23","DOI":"10.4230\/LIPIcs.CPM.2019.23"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-86692-1_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T21:25:56Z","timestamp":1632777956000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86692-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030866914","9783030866921"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86692-1_7","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":"27 September 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lille","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","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":"4 October 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 October 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cristal.univ-lille.fr\/spire2021\/","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":"30","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":"14","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":"4","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":"47% - 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.87","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.32","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)"}},{"value":"2 invited papers are also included. The symposium was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}