On the Impact of Morphisms on BWT-Runs

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="google" content="notranslate"> <meta http-equiv="Content-Language" content="en"> <meta name="viewport" content="width=device-width, initial-scale=1"> <meta name="csrf-token" content="GIW0u8szKfjsmBbSijzyXWhLlbKZ85APAuuWLDQq"> <link rel="canonical" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10"> <meta name="DC.Publisher" content="Schloss Dagstuhl – Leibniz-Zentrum für Informatik" > <meta name="DC.Title" xml:lang="en" content="On the Impact of Morphisms on BWT-Runs" > <meta name="DC.Creator.PersonalName" content="Fici, Gabriele" > <meta name="DC.Creator.PersonalName" content="Romana, Giuseppe" > <meta name="DC.Creator.PersonalName" content="Sciortino, Marinella" > <meta name="DC.Creator.PersonalName" content="Urbina, Cristian" > <meta name="DC.Subject" content="Morphism" > <meta name="DC.Subject" content="Burrows-Wheeler transform" > <meta name="DC.Subject" content="Sturmian word" > <meta name="DC.Subject" content="Sturmian morphism" > <meta name="DC.Subject" content="Thue-Morse morphism" > <meta name="DC.Subject" content="Repetitiveness measure" > <meta name="DC.Date.created" scheme="ISO8601" content="2023-06-21" > <meta name="DC.Date.issued" scheme="ISO8601" content="2023-06-21" > <meta name="DC.Date.modified" scheme="ISO8601" content="2023-06-21" > <meta name="DC.Type" content="InProceedings" > <meta name="DC.Format" scheme="IMT" content="application/pdf" > <meta name="DC.Identifier" scheme="urn:nbn:de" content="urn:nbn:de:0030-drops-179641" > <meta name="DC.Identifier" scheme="DOI" content="10.4230/LIPIcs.CPM.2023.10" > <meta name="DC.Identifier" scheme="URL" content="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10" > <meta name="DC.Source" content="34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)" > <meta name="DC.Source.URI" content="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259" > <meta name="DC.Language" scheme="ISO639-1" content="en" > <meta name="DC.Description" xml:lang="en" content="Morphisms are widely studied combinatorial objects that can be used for generating infinite families of words. In the context of Information theory, injective morphisms are called (variable length) codes. In Data compression, the morphisms, combined with parsing techniques, have been recently used to define new mechanisms to generate repetitive words. Here, we show that the repetitiveness induced by applying a morphism to a word can be captured by a compression scheme based on the Burrows-Wheeler Transform (BWT). In fact, we prove that, differently from other compression-based repetitiveness measures, the measure r_bwt (which counts the number of equal-letter runs produced by applying BWT to a word) strongly depends on the applied morphism. More in detail, we characterize the binary morphisms that preserve the value of r_bwt(w), when applied to any binary word w containing both letters. They are precisely the Sturmian morphisms, which are well-known objects in Combinatorics on words. Moreover, we prove that it is always possible to find a binary morphism that, when applied to any binary word containing both letters, increases the number of BWT-equal letter runs by a given (even) number. In addition, we derive a method for constructing arbitrarily large families of binary words on which BWT produces a given (even) number of new equal-letter runs. Such results are obtained by using a new class of morphisms that we call Thue-Morse-like. Finally, we show that there exist binary morphisms μ for which it is possible to find words w such that the difference r_bwt(μ(w))-r_bwt(w) is arbitrarily large." > <meta name="DC.Rights" scheme="DCTERMS.URI" content="https://creativecommons.org/licenses/by/4.0/legalcode" > <meta name="citation_conference_title" content="34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)" > <meta name="citation_doi" content="10.4230/LIPIcs.CPM.2023.10" > <meta name="citation_firstpage" content="10:1" > <meta name="citation_lastpage" content="10:18" > <meta name="citation_title" content="On the Impact of Morphisms on BWT-Runs" > <meta name="citation_language" content="en" > <meta name="citation_keyword" content="Morphism" > <meta name="citation_keyword" content="Burrows-Wheeler transform" > <meta name="citation_keyword" content="Sturmian word" > <meta name="citation_keyword" content="Sturmian morphism" > <meta name="citation_keyword" content="Thue-Morse morphism" > <meta name="citation_keyword" content="Repetitiveness measure" > <meta name="citation_author" content="Fici, Gabriele" > <meta name="citation_author_institution" content="Department of Mathematics and Informatics, University of Palermo, Italy" > <meta name="citation_author" content="Romana, Giuseppe" > <meta name="citation_author_institution" content="Department of Mathematics and Informatics, University of Palermo, Italy" > <meta name="citation_author" content="Sciortino, Marinella" > <meta name="citation_author_institution" content="Department of Mathematics and Informatics, University of Palermo, Italy" > <meta name="citation_author" content="Urbina, Cristian" > <meta name="citation_author_institution" content="Department of Computer Science, University of Chile, Santiago, Chile; Centre for Biotechnology and Bioengineering (CeBiB), Santiago, Chile" > <meta name="citation_date" content="2023" > <meta name="citation_keyword" xml:lang="en" content="Morphism" > <meta name="citation_keyword" xml:lang="en" content="Burrows-Wheeler transform" > <meta name="citation_keyword" xml:lang="en" content="Sturmian word" > <meta name="citation_keyword" xml:lang="en" content="Sturmian morphism" > <meta name="citation_keyword" xml:lang="en" content="Thue-Morse morphism" > <meta name="citation_keyword" xml:lang="en" content="Repetitiveness measure" > <meta name="citation_abstract_html_url" content="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10" > <meta name="citation_pdf_url" content="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.10/LIPIcs.CPM.2023.10.pdf" > <meta name="citation_reference" content="Tooru Akagi, Mitsuru Funakoshi, and Shunsuke Inenaga. Sensitivity of string compressors and repetitiveness measures. Inf. Comput., 291:104999, 2023." > <meta name="citation_reference" content="Jean Berstel, Dominique Perrin, and Christophe Reutenauer. Codes and Automata, volume 129 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2010." > <meta name="citation_reference" content="Jean Berstel and Patrice Séébold. A characterization of sturmian morphisms. In MFCS, volume 711 of Lecture Notes in Computer Science, pages 281-290. Springer, 1993." > <meta name="citation_reference" content="Srecko Brlek, Andrea Frosini, Ilaria Mancini, Elisa Pergola, and Simone Rinaldi. Burrows-wheeler transform of words defined by morphisms. In IWOCA, volume 11638 of Lecture Notes in Computer Science, pages 393-404. Springer, 2019." > <meta name="citation_reference" content="Michael Burrows and David Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994." > <meta name="citation_reference" content="Julien Cassaigne. Sequences with grouped factors. In DLT, pages 211-222. Aristotle University of Thessaloniki, 1997." > <meta name="citation_reference" content="Giusi Castiglione, Antonio Restivo, and Marinella Sciortino. Circular Sturmian words and Hopcroft’s algorithm. Theor. Comput. Sci., 410(43):4372-4381, 2009." > <meta name="citation_reference" content="Wai-Fong Chuan. Sturmian morphisms and alpha-words. Theor. Comput. Sci., 225(1-2):129-148, 1999." > <meta name="citation_reference" content="Sorin Constantinescu and Lucian Ilie. The lempel-ziv complexity of fixed points of morphisms. SIAM J. Discret. Math., 21(2):466-481, 2007." > <meta name="citation_reference" content="Maxime Crochemore, Thierry Lecroq, and Wojciech Rytter. 125 Problems in Text Algorithms: with Solutions. Cambridge University Press, 2021." > <meta name="citation_reference" content="Paolo Ferragina and Giovanni Manzini. Opportunistic Data Structures with Applications. In FOCS, pages 390-398. IEEE Computer Society, 2000." > <meta name="citation_reference" content="Andrea Frosini, Ilaria Mancini, Simone Rinaldi, Giuseppe Romana, and Marinella Sciortino. Logarithmic equal-letter runs for BWT of purely morphic words. In DLT, volume 13257 of Lect. Notes Comput. Sc., pages 139-151. Springer, 2022." > <meta name="citation_reference" content="Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space. J. ACM, 67(1):2:1-2:54, 2020." > <meta name="citation_reference" content="Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Nicola Prezza, Marinella Sciortino, and Anna Toffanello. Novel results on the number of runs of the burrows-wheeler-transform. In SOFSEM, volume 12607 of Lecture Notes in Computer Science, pages 249-262. Springer, 2021." > <meta name="citation_reference" content="Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Giuseppe Romana, Marinella Sciortino, and Cristian Urbina. Bit catastrophes for the Burrows-Wheeler Transform. In DLT, volume 13911 of Lect. Notes Comput. Sc. Springer, 2023." > <meta name="citation_reference" content="Dominik Kempa and Tomasz Kociumaka. Resolution of the Burrows-Wheeler Transform Conjecture. Commun. ACM, 65(6):91-98, 2022." > <meta name="citation_reference" content="Takuya Kida, Tetsuya Matsumoto, Yusuke Shibata, Masayuki Takeda, Ayumi Shinohara, and Setsuo Arikawa. Collage system: a unifying framework for compressed pattern matching. Theor. Comput. Sci., 298(1):253-272, 2003." > <meta name="citation_reference" content="John C. Kieffer and En-Hui Yang. Grammar-based codes: A new class of universal lossless source codes. IEEE Trans. Inf. Theory, 46(3):737-754, 2000." > <meta name="citation_reference" content="Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323-350, 1977." > <meta name="citation_reference" content="Sebastian Kreft and Gonzalo Navarro. LZ77-Like Compression with Fast Random Access. In DCC, pages 239-248. IEEE, 2010." > <meta name="citation_reference" content="Ben Langmead and Steven Salzberg. Fast gapped-read alignment with Bowtie 2. Nature methods, 9:357-359, March 2012." > <meta name="citation_reference" content="Abraham Lempel and Jacob Ziv. On the complexity of finite sequences. IEEE Trans. Inf. Theory, 22(1):75-81, 1976." > <meta name="citation_reference" content="Heng Li and Richard Durbin. Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinform., 26(5):589-595, 2010." > <meta name="citation_reference" content="M. Lothaire. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, New York, NY, USA, 2002." > <meta name="citation_reference" content="Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, Marinella Sciortino, and Luca Versari. Measuring the clustering effect of BWT via RLE. Theoret. Comput. Sci., 698:79-87, 2017." > <meta name="citation_reference" content="Sabrina Mantaci, Antonio Restivo, and Marinella Sciortino. Burrows-Wheeler transform and Sturmian words. Inf. Process. Lett., 86(5):241-246, 2003. URL: https://doi.org/10.1016/S0020-0190(02)00512-4." > <meta name="citation_reference" content="Giovanni Manzini. An analysis of the Burrows-Wheeler transform. J. ACM, 48(3):407-430, 2001." > <meta name="citation_reference" content="Filippo Mignosi and Patrice Séébold. Morphismes sturmiens et règles de Rauzy. Journal de théorie des nombres de Bordeaux, 5(2):221-233, 1993." > <meta name="citation_reference" content="Gonzalo Navarro. Indexing highly repetitive string collections, part I: Repetitiveness measures. ACM Computing Surveys, 54(2):article 29, 2021." > <meta name="citation_reference" content="Gonzalo Navarro. The compression power of the BWT: technical perspective. Commun. ACM, 65(6):90, 2022." > <meta name="citation_reference" content="Gonzalo Navarro, Carlos Ochoa, and Nicola Prezza. On the approximation ratio of ordered parsings. IEEE Trans. Inf. Theory, 67(2):1008-1026, 2021." > <meta name="citation_reference" content="Gonzalo Navarro and Cristian Urbina. On stricter reachable repetitiveness measures. In SPIRE, volume 12944 of Lect. Notes Comput. Sci., pages 193-206. Springer, 2021." > <meta name="citation_reference" content="Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Fully Dynamic Data Structure for LCE Queries in Compressed Space. In MFCS, volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), pages 72:1-72:15, 2016." > <meta name="citation_reference" content="Geneviève Paquin. On a generalization of Christoffel words: epichristoffel words. Theor. Comput. Sci., 410(38-40):3782-3791, 2009. URL: https://doi.org/10.1016/j.tcs.2009.05.014." > <meta name="citation_reference" content="Antonio Restivo and Giovanna Rosone. Balancing and clustering of words in the Burrows-Wheeler transform. Theor. Comput. Sci., 412(27):3019-3032, 2011. URL: https://doi.org/10.1016/j.tcs.2010.11.040." > <meta name="citation_reference" content="Grzegorz Rozenberg and Arto Salomaa. The mathematical theory of L systems. Academic press, 1980." > <meta name="citation_reference" content="Marinella Sciortino and Luca Q. Zamboni. Suffix automata and standard sturmian words. In DLT, volume 4588 of Lect. Notes Comput. Sc., pages 382-398. Springer, 2007." > <meta name="citation_reference" content="James A. Storer and Thomas G. Szymanski. Data compression via textual substitution. J. ACM, !month = oct, 29(4):928-951, 1982." > <meta name="citation_publisher" content="Schloss Dagstuhl – Leibniz-Zentrum für Informatik" > <script type="application/ld+json"> { "@context": "https://schema.org/", "@type": "WebPage", "mainEntity": { "@type": "ScholarlyArticle", "url": "https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10", "headline": "On the Impact of Morphisms on BWT-Runs", "name": "On the Impact of Morphisms on BWT-Runs", "abstract": "Morphisms are widely studied combinatorial objects that can be used for generating infinite families of words. In the context of Information theory, injective morphisms are called (variable length) codes. In Data compression, the morphisms, combined with parsing techniques, have been recently used to define new mechanisms to generate repetitive words. Here, we show that the repetitiveness induced by applying a morphism to a word can be captured by a compression scheme based on the Burrows-Wheeler Transform (BWT). In fact, we prove that, differently from other compression-based repetitiveness measures, the measure r_bwt (which counts the number of equal-letter runs produced by applying BWT to a word) strongly depends on the applied morphism. More in detail, we characterize the binary morphisms that preserve the value of r_bwt(w), when applied to any binary word w containing both letters. They are precisely the Sturmian morphisms, which are well-known objects in Combinatorics on words. Moreover, we prove that it is always possible to find a binary morphism that, when applied to any binary word containing both letters, increases the number of BWT-equal letter runs by a given (even) number. In addition, we derive a method for constructing arbitrarily large families of binary words on which BWT produces a given (even) number of new equal-letter runs. Such results are obtained by using a new class of morphisms that we call Thue-Morse-like. Finally, we show that there exist binary morphisms \u03bc for which it is possible to find words w such that the difference r_bwt(\u03bc(w))-r_bwt(w) is arbitrarily large.", "keywords": [ "Morphism", "Burrows-Wheeler transform", "Sturmian word", "Sturmian morphism", "Thue-Morse morphism", "Repetitiveness measure" ], "author": [ { "@type": "Person", "name": "Fici, Gabriele", "givenName": "Gabriele", "familyName": "Fici", "email": "mailto:gabriele.fici@unipa.it", "sameAs": "https://orcid.org/0000-0002-3536-327X", "affiliation": "Department of Mathematics and Informatics, University of Palermo, Italy", "funding": "Partly supported by MIUR project PRIN 2017 ADASCOML - 2017K7XPAN." }, { "@type": "Person", "name": "Romana, Giuseppe", "givenName": "Giuseppe", "familyName": "Romana", "email": "mailto:giuseppe.romana01@unipa.it", "sameAs": "https://orcid.org/0000-0002-3489-0684", "affiliation": "Department of Mathematics and Informatics, University of Palermo, Italy", "funding": "Partly supported by MIUR project PRIN 2017 ADASCOML - 2017K7XPAN." }, { "@type": "Person", "name": "Sciortino, Marinella", "givenName": "Marinella", "familyName": "Sciortino", "email": "mailto:marinella.sciortino@unipa.it", "sameAs": "https://orcid.org/0000-0001-6928-0168", "affiliation": "Department of Mathematics and Informatics, University of Palermo, Italy", "funding": "Partly supported by the INdAM-GNCS Project (CUP E55F22000270001) and the PNRR project ITSERR (CUP B53C22001770006)." }, { "@type": "Person", "name": "Urbina, Cristian", "givenName": "Cristian", "familyName": "Urbina", "email": "mailto:crurbina@dcc.uchile.cl", "sameAs": "https://orcid.org/0000-0001-8979-9055", "affiliation": "Department of Computer Science, University of Chile, Santiago, Chile", "funding": "Partly supported by ANID national doctoral scholarship - 21210580." } ], "position": 10, "dateCreated": "2023-06-21", "datePublished": "2023-06-21", "isAccessibleForFree": true, "license": "https://creativecommons.org/licenses/by/4.0/legalcode", "copyrightHolder": [ { "@type": "Person", "name": "Fici, Gabriele", "givenName": "Gabriele", "familyName": "Fici", "email": "mailto:gabriele.fici@unipa.it", "sameAs": "https://orcid.org/0000-0002-3536-327X", "affiliation": "Department of Mathematics and Informatics, University of Palermo, Italy", "funding": "Partly supported by MIUR project PRIN 2017 ADASCOML - 2017K7XPAN." }, { "@type": "Person", "name": "Romana, Giuseppe", "givenName": "Giuseppe", "familyName": "Romana", "email": "mailto:giuseppe.romana01@unipa.it", "sameAs": "https://orcid.org/0000-0002-3489-0684", "affiliation": "Department of Mathematics and Informatics, University of Palermo, Italy", "funding": "Partly supported by MIUR project PRIN 2017 ADASCOML - 2017K7XPAN." }, { "@type": "Person", "name": "Sciortino, Marinella", "givenName": "Marinella", "familyName": "Sciortino", "email": "mailto:marinella.sciortino@unipa.it", "sameAs": "https://orcid.org/0000-0001-6928-0168", "affiliation": "Department of Mathematics and Informatics, University of Palermo, Italy", "funding": "Partly supported by the INdAM-GNCS Project (CUP E55F22000270001) and the PNRR project ITSERR (CUP B53C22001770006)." }, { "@type": "Person", "name": "Urbina, Cristian", "givenName": "Cristian", "familyName": "Urbina", "email": "mailto:crurbina@dcc.uchile.cl", "sameAs": "https://orcid.org/0000-0001-8979-9055", "affiliation": "Department of Computer Science, University of Chile, Santiago, Chile", "funding": "Partly supported by ANID national doctoral scholarship - 21210580." } ], "copyrightYear": "2023", "creativeWorkStatus": "Published", "inLanguage": "en-US", "identifier": "https://doi.org/10.4230/LIPIcs.CPM.2023.10", "publisher": { "@type": "Organization", "name": "Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik", "alternateName": [ "Schloss Dagstuhl - Leibniz Center for Informatics", "Schloss Dagstuhl - LZI GmbH" ], "identifier": "https://ror.org/00k4h2615", "sameAs": [ "https://isni.org/isni/0000000100093196", "https://www.dagstuhl.de", "https://de.wikipedia.org/wiki/Leibniz-Zentrum_f%C3%BCr_Informatik" ], "department": { "@type": "Organization", "name": "Dagstuhl Publishing", "logo": { "@type": "ImageObject", "url": "https://www.dagstuhl.de/storage/media/0005/5660/publishing-logo.jpg" }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:publishing@dagstuhl.de", "url": "https://www.dagstuhl.de/en/publishing/team" } }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:lzi@dagstuhl.de", "url": "https://www.dagstuhl.de/en/institute/team" } }, "citation": [ "https://doi.org/10.1016/S0020-0190(02)00512-4", "https://doi.org/10.1016/j.tcs.2009.05.014", "https://doi.org/10.1016/j.tcs.2010.11.040" ], "pageStart": "10:1", "pageEnd": "10:18", "accessMode": "textual", "accessModeSufficient": "textual", "thumbnailUrl": "https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/thumbnails/LIPIcs.CPM.2023.10/LIPIcs.CPM.2023.10.png", "potentialAction": { "@type": "ReadAction", "target": { "@type": "EntryPoint", "urlTemplate": "https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10", "actionPlatform": [ "https://schema.org/DesktopWebPlatform", "https://schema.org/AndroidPlatform", "https://schema.org/IOSPlatform" ] } }, "isPartOf": { "@type": "PublicationVolume", "@id": "https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259", "url": "https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259", "volumeNumber": 259, "name": "34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)", "dateCreated": "2023-06-21", "datePublished": "2023-06-21", "editor": [ { "@type": "Person", "name": "Bulteau, Laurent", "givenName": "Laurent", "familyName": "Bulteau", "email": "mailto:laurent.bulteau@univ-eiffel.fr", "sameAs": "https://orcid.org/0000-0003-1645-9345", "affiliation": "LIGM, CNRS, Universit\u00e9 Gustave Eiffel, Marne-la-vall\u00e9e, France" }, { "@type": "Person", "name": "Lipt\u00e1k, Zsuzsanna", "givenName": "Zsuzsanna", "familyName": "Lipt\u00e1k", "email": "mailto:zsuzsanna.liptak@univr.it", "sameAs": "https://orcid.org/0000-0002-3233-0691", "affiliation": "University of Verona, Italy" } ], "isAccessibleForFree": true, "publisher": { "@type": "Organization", "name": "Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik", "alternateName": [ "Schloss Dagstuhl - Leibniz Center for Informatics", "Schloss Dagstuhl - LZI GmbH" ], "identifier": "https://ror.org/00k4h2615", "sameAs": [ "https://isni.org/isni/0000000100093196", "https://www.dagstuhl.de", "https://de.wikipedia.org/wiki/Leibniz-Zentrum_f%C3%BCr_Informatik" ], "department": { "@type": "Organization", "name": "Dagstuhl Publishing", "logo": { "@type": "ImageObject", "url": "https://www.dagstuhl.de/storage/media/0005/5660/publishing-logo.jpg" }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:publishing@dagstuhl.de", "url": "https://www.dagstuhl.de/en/publishing/team" } }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:lzi@dagstuhl.de", "url": "https://www.dagstuhl.de/en/institute/team" } }, "isPartOf": { "@type": "BookSeries", "url": "https://drops.dagstuhl.de/entities/series/LIPIcs", "name": "Leibniz International Proceedings in Informatics", "issn": "1868-8969", "isAccessibleForFree": true, "publisher": { "@type": "Organization", "name": "Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik", "alternateName": [ "Schloss Dagstuhl - Leibniz Center for Informatics", "Schloss Dagstuhl - LZI GmbH" ], "identifier": "https://ror.org/00k4h2615", "sameAs": [ "https://isni.org/isni/0000000100093196", "https://www.dagstuhl.de", "https://de.wikipedia.org/wiki/Leibniz-Zentrum_f%C3%BCr_Informatik" ], "department": { "@type": "Organization", "name": "Dagstuhl Publishing", "logo": { "@type": "ImageObject", "url": "https://www.dagstuhl.de/storage/media/0005/5660/publishing-logo.jpg" }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:publishing@dagstuhl.de", "url": "https://www.dagstuhl.de/en/publishing/team" } }, "contactPoint": { "@type": "ContactPoint", "contactType": "customer support", "email": "mailto:lzi@dagstuhl.de", "url": "https://www.dagstuhl.de/en/institute/team" } }, "hasPart": "https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259" } } } } </script> <link rel="alternate" type="application/xml" title="On the Impact of Morphisms on BWT-Runs / XML" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10/metadata/xml"> <link rel="alternate" type="application/x-bibtex" title="On the Impact of Morphisms on BWT-Runs / BibTeX" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10/metadata/bibtex/download"> <link rel="alternate" type="application/ld+json" title="On the Impact of Morphisms on BWT-Runs / Schema.org" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10/metadata/schema-org"> <link rel="alternate" type="application/xml" title="On the Impact of Morphisms on BWT-Runs / OAI-DublinCore" href="/oai/?verb=GetRecord&metadataPrefix=oai_dc&identifier=17964"> <title>On the Impact of Morphisms on BWT-Runs</title> <link rel="icon" href="https://drops.dagstuhl.de/favicon.ico"> <link rel="stylesheet" href="https://drops.dagstuhl.de/css/app.css?drops-core-2025-01-23.1"> </head> <body> <nav class="navbar main fixed-top navbar-expand-lg navbar-light bg-light"> <div class="container-fluid"> <a class="navbar-brand" href="https://www.dagstuhl.de"> <img class="lzi-logo" src="https://drops.dagstuhl.de/images/LZI-Logo.jpg" width="84" height="62" alt="Schloss Dagstuhl - LZI - Logo"> </a> <button class="navbar-toggler" type="button" data-bs-toggle="collapse" data-bs-target="#navbarSupportedContent" aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="collapse navbar-collapse" id="navbarSupportedContent"> <ul class="navbar-nav me-auto mb-2 mb-lg-0"> <li class="nav-item" style="white-space: nowrap"> <a class="nav-link" href="https://drops.dagstuhl.de"> <i class="bi bi-house large-icon"></i> DROPS </a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownSeries" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journals large-icon"></i> Series </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/LIPIcs"> LIPIcs – Leibniz International Proceedings in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/OASIcs"> OASIcs – Open Access Series in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DFU"> Dagstuhl Follow-Ups </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DagAnnRep"> Schloss Dagstuhl Jahresbericht </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/#discontinued-series">Discontinued Series</a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownJournals" role="button" data-bs-toggle="dropdown" aria-expanded="false" data-fix-width=" JournalsXXXXX "> <i class="bi bi-journal large-icon"></i> Journals </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DARTS"> DARTS – Dagstuhl Artifacts Series </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagRep"> Dagstuhl Reports </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagMan"> Dagstuhl Manifestos </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/LITES"> LITES – Leibniz Transactions on Embedded Systems </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/TGDK"> TGDK – Transactions on Graph Data and Knowledge </a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownConferences" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-people large-icon"></i> Conferences </a> <ul class="dropdown-menu conference-dropdown" aria-labelledby="navbarDropdown"> <div class="row"> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AFT"> AFT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AIB"> AIB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AofA"> AofA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/APPROX"> APPROX </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ATMOS"> ATMOS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CALCO"> CALCO </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CCC"> CCC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CONCUR"> CONCUR </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/COSIT"> COSIT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CP"> CP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CPM"> CPM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CSL"> CSL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DISC"> DISC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DITAM"> DITAM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DNA"> DNA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECOOP"> ECOOP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECRTS"> ECRTS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ESA"> ESA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FAB"> FAB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FMBC"> FMBC </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FORC"> FORC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSCD"> FSCD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSTTCS"> FSTTCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FUN"> FUN </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GD"> GD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GIScience"> GIScience </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICALP"> ICALP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICDT"> ICDT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICPEC"> ICPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/IPEC"> IPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/iPMVM"> iPMVM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ISAAC"> ISAAC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITC"> ITC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITCS"> ITCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITP"> ITP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/LDK"> LDK </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/MFCS"> MFCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Microservices"> Microservices </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/NG-RES"> NG-RES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/OPODIS"> OPODIS </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/PARMA"> PARMA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/RANDOM"> RANDOM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAND"> SAND </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAT"> SAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SEA"> SEA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SLATE"> SLATE </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SNAPL"> SNAPL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SoCG"> SoCG </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/STACS"> STACS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SWAT"> SWAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TIME"> TIME </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Tokenomics"> Tokenomics </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TQC"> TQC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TYPES"> TYPES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WABI"> WABI </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WCET"> WCET </a> </li> </div> </div> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownArtifacts" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-braces-asterisk large-icon"></i> Artifacts </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/collection/supplementary-materials"> Supplementary Materials (Software, Datasets, ...) </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/collection/dblp"> dblp Artifacts </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/entities/journal/DARTS"> DARTS (Evaluated Artifacts) </a> </li> </ul> </li> </ul> <form class="navbar-search d-flex" action="https://drops.dagstuhl.de/search" method="post"> <input type="hidden" name="_token" value="GIW0u8szKfjsmBbSijzyXWhLlbKZ85APAuuWLDQq" autocomplete="off"> <div class="input-group"> <input class="form-control" type="search" placeholder="Search" aria-label="Search" name="term" autocomplete="off" maxlength="600"> <button class="btn btn-outline-success" type="submit"> <i class="bi bi-search" style="color: #000"></i> </button> </div> </form> <ul class="navbar-nav nav-metadata"> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" id="navbarDropdownMetadata" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-database-down large-icon"></i><span class="nav-text-metadata">Metadata Export</span> </a> <ul class="dropdown-menu dropdown-metadata" aria-labelledby="navbarDropdownMetadata"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/metadata">Metadata Export</a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/oai?verb=Identify" target="_blank">OAI Interface</a> </li> </ul> </li> </ul> </div> </div> </nav> <div id="app" data-release="drops-core-2025-01-23.1" class="container "> <div id="_top-of-page"></div> <div class="fixed-search-button"><i class="bi bi-search"></i></div> <div class="document-details"> <section class="mt-3 mb-5 title"> <div class="entity-type document"> <div class="row"> <div class="col-lg-3 entity-type-name"> <i class="bi bi-file-earmark"></i> Document <img src="https://drops.dagstuhl.de/images/open-access-logo.png" width="80" alt="Open Access Logo" style="transform: translate(1em, -0.2em);"> </div> <div class="col-lg-9"> <input id="doi" type="text" style="position: fixed; top: -50vh" value="https://doi.org/10.4230/LIPIcs.CPM.2023.10"> <div class="sharing-section"> <span class="permalink"> <span> <code><span class="hide-mobile">https://doi.org/</span>10.4230/LIPIcs.CPM.2023.10</code> <span class="btn btn-clipboard copy-to-clipboard" title="Copy to clipboard" data-selector="doi"> <i class="bi bi-clipboard" aria-hidden="true"></i> <i class="bi bi-check -hidden" aria-hidden="true"></i> </span> </span> </span> <span class="sharing-buttons"> <a class="btn sharing-btn facebook" href="https://facebook.com/sharer/sharer.php?u=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.CPM.2023.10" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-facebook"></i> </a> <a class="btn sharing-btn reddit" href="https://www.reddit.com/submit?url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.CPM.2023.10&title=On+the+Impact+of+Morphisms+on+BWT-Runs" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-reddit"></i> </a> <a class="btn sharing-btn twitter" href="https://twitter.com/intent/tweet/?text=On+the+Impact+of+Morphisms+on+BWT-Runs&url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.CPM.2023.10" target="_blank" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-twitter-x" viewBox="0 0 16 16"> <path d="M12.6.75h2.454l-5.36 6.142L16 15.25h-4.937l-3.867-5.07-4.425 5.07H.316l5.733-6.57L0 .75h5.063l3.495 4.633L12.601.75Zm-.86 13.028h1.36L4.323 2.145H2.865l8.875 11.633Z"/> </svg> </a> <a class="btn sharing-btn email" href="mailto:?subject=On+the+Impact+of+Morphisms+on+BWT-Runs&body=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.CPM.2023.10" target="_self" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" viewBox="0 0 24 24" fill="currentColor"> <path d="M22 4H2C.9 4 0 4.9 0 6v12c0 1.1.9 2 2 2h20c1.1 0 2-.9 2-2V6c0-1.1-.9-2-2-2zM7.25 14.43l-3.5 2c-.08.05-.17.07-.25.07-.17 0-.34-.1-.43-.25-.14-.24-.06-.55.18-.68l3.5-2c.24-.14.55-.06.68.18.14.24.06.55-.18.68zm4.75.07c-.1 0-.2-.03-.27-.08l-8.5-5.5c-.23-.15-.3-.46-.15-.7.15-.22.46-.3.7-.14L12 13.4l8.23-5.32c.23-.15.54-.08.7.15.14.23.07.54-.16.7l-8.5 5.5c-.08.04-.17.07-.27.07zm8.93 1.75c-.1.16-.26.25-.43.25-.08 0-.17-.02-.25-.07l-3.5-2c-.24-.13-.32-.44-.18-.68s.44-.32.68-.18l3.5 2c.24.13.32.44.18.68z"/> </svg> </a> </span> <span class="sharing-buttons"> <span class="dropdown"> <a class="btn sharing-btn metadata dropdown-toggle" href="#" role="button" data-bs-toggle="dropdown" aria-expanded="false"><i class="bi bi-download"></i></a> <ul class="dropdown-menu dropdown-menu-end"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10/metadata/xml"> Export XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10/metadata/acm-xml"> Export ACM-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10/metadata/doaj-xml"> Export DOAJ-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10/metadata/schema-org"> Export Schema.org </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10/metadata/bibtex"> Export BibTeX </a> </li> </ul> </span> </span> </div> </div> </div> </div> <hr> <h1>On the Impact of Morphisms on BWT-Runs</h1> <h3 class="mt-2 authors"> Authors <a href="#author-details" style="font-size: 0.8em; padding-right: 1em"><i class="bi bi-info-circle"></i></a> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Fici, Gabriele" class="name">Gabriele Fici</a> <a href="https://orcid.org/0000-0002-3536-327X"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Romana, Giuseppe" class="name">Giuseppe Romana</a> <a href="https://orcid.org/0000-0002-3489-0684"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Sciortino, Marinella" class="name">Marinella Sciortino</a> <a href="https://orcid.org/0000-0001-6928-0168"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Urbina, Cristian" class="name">Cristian Urbina</a> <a href="https://orcid.org/0000-0001-8979-9055"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> </span> </h3> <hr> <ul class="mt-4"> <li> <span style="margin-right: 10px; ">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-book-half"></i> Volume: </span> <a href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259">34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) </a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-journals"></i> Series: </span> <a href="https://drops.dagstuhl.de/entities/series/LIPIcs">Leibniz International Proceedings in Informatics (LIPIcs)</a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-people"></i> Conference: </span> <a href="https://drops.dagstuhl.de/entities/conference/CPM">Annual Symposium on Combinatorial Pattern Matching (CPM)</a> </li> <li class="mt-2">License:   <a href="https://creativecommons.org/licenses/by/4.0/legalcode"> <img class="license-logo" src="https://drops.dagstuhl.de/images/cc-by.png" alt="CC-BY Logo"> Creative Commons Attribution 4.0 International license </a> </li> <li>Publication Date: 2023-06-21 </li> </ul> <hr> </section> <a class="fixed-pdf-button" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.10/LIPIcs.CPM.2023.10.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> PDF </a> <div class="row mt-2"> <div class="col-lg-4 mt-2"> <section class="thumbnail"> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.10/LIPIcs.CPM.2023.10.pdf"><img src="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/thumbnails/LIPIcs.CPM.2023.10/LIPIcs.CPM.2023.10.png" alt="Thumbnail PDF"></a> </section> <section class="files mt-5"> <h2>File</h2> <div class="content"> <div> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.10/LIPIcs.CPM.2023.10.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> LIPIcs.CPM.2023.10.pdf</a> <ul> <li>Filesize: 0.78 MB</li> <li>18 pages</li> </ul> </div> </div> </section> <section class="identifiers mt-3"> <h2>Document Identifiers</h2> <div class="content"> <ul> <li><b>DOI:</b> <a href="https://doi.org/10.4230/LIPIcs.CPM.2023.10">10.4230/LIPIcs.CPM.2023.10</a></li> <li><b>URN:</b> <a href="https://nbn-resolving.org/process-urn-form?identifier=urn:nbn:de:0030-drops-179641&verb=FULL">urn:nbn:de:0030-drops-179641</a></li> </ul> </div> </section> <section class="authors mt-3" id="author-details"> <h2>Author Details</h2> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Gabriele Fici</b></span> <a href="https://orcid.org/0000-0002-3536-327X"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:gabriele.fici@unipa.it"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Fici, Gabriele"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Mathematics and Informatics, University of Palermo, Italy </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Giuseppe Romana</b></span> <a href="https://orcid.org/0000-0002-3489-0684"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:giuseppe.romana01@unipa.it"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Romana, Giuseppe"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Mathematics and Informatics, University of Palermo, Italy </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Marinella Sciortino</b></span> <a href="https://orcid.org/0000-0001-6928-0168"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:marinella.sciortino@unipa.it"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Sciortino, Marinella"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Mathematics and Informatics, University of Palermo, Italy </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Cristian Urbina</b></span> <a href="https://orcid.org/0000-0001-8979-9055"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:crurbina@dcc.uchile.cl"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Urbina, Cristian"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Computer Science, University of Chile, Santiago, Chile </li> <li class="affiliation">Centre for Biotechnology and Bioengineering (CeBiB), Santiago, Chile </li> </ul> </div> </section> <section class="related-version mt-3"> <h2>Funding</h2> <div class="content"> <ul> <li><b>Fici, Gabriele</b>: Partly supported by MIUR project PRIN 2017 ADASCOML - 2017K7XPAN.</li> <li><b>Romana, Giuseppe</b>: Partly supported by MIUR project PRIN 2017 ADASCOML - 2017K7XPAN.</li> <li><b>Sciortino, Marinella</b>: Partly supported by the INdAM-GNCS Project (CUP E55F22000270001) and the PNRR project ITSERR (CUP B53C22001770006).</li> <li><b>Urbina, Cristian</b>: Partly supported by ANID national doctoral scholarship - 21210580.</li> </ul> </div> </section> <section class="acknowledgements mt-3"> <h2>Acknowledgements</h2> <div class="content"> This research was carried out during the visit of Cristian Urbina to the University of Palermo, Italy. </div> </section> </div> <div class="col-lg-8 mt-2"> <section class="cite-as mt-3"> <h2>Cite As <span class="btn btn-primary btn-xs" style="float: right" data-bs-toggle="modal" data-bs-target="#bibtex-modal">Get BibTex</span></h2> <div class="content"> Gabriele Fici, Giuseppe Romana, Marinella Sciortino, and Cristian Urbina. On the Impact of Morphisms on BWT-Runs. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) <a href="https://doi.org/10.4230/LIPIcs.CPM.2023.10">https://doi.org/10.4230/LIPIcs.CPM.2023.10</a> </div> <div class="modal fade" id="bibtex-modal" tabindex="-1" aria-labelledby="bibtexModalLabel" aria-hidden="true"> <div class="modal-dialog modal-dialog-centered"> <div class="modal-content"> <div class="modal-header"> <h5 class="modal-title" id="bibtexModalLabel">BibTex</h5> <button type="button" class="btn-close" data-bs-dismiss="modal" aria-label="Close"></button> </div> <div class="modal-body"> <pre class="bibtex">@InProceedings{fici_et_al:LIPIcs.CPM.2023.10, author = {Fici, Gabriele and Romana, Giuseppe and Sciortino, Marinella and Urbina, Cristian}, title = {{On the Impact of Morphisms on BWT-Runs}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-276-1}, ISSN = {1868-8969}, year = {2023}, volume = {259}, editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10}, URN = {urn:nbn:de:0030-drops-179641}, doi = {10.4230/LIPIcs.CPM.2023.10}, annote = {Keywords: Morphism, Burrows-Wheeler transform, Sturmian word, Sturmian morphism, Thue-Morse morphism, Repetitiveness measure} }</pre> <div style="overflow: hidden"> <textarea style="position: absolute; top: -400vh" id="bibtex-input">@InProceedings{fici_et_al:LIPIcs.CPM.2023.10, author = {Fici, Gabriele and Romana, Giuseppe and Sciortino, Marinella and Urbina, Cristian}, title = {{On the Impact of Morphisms on BWT-Runs}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-276-1}, ISSN = {1868-8969}, year = {2023}, volume = {259}, editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10}, URN = {urn:nbn:de:0030-drops-179641}, doi = {10.4230/LIPIcs.CPM.2023.10}, annote = {Keywords: Morphism, Burrows-Wheeler transform, Sturmian word, Sturmian morphism, Thue-Morse morphism, Repetitiveness measure} }</textarea> </div> </div> <div class="modal-footer"> <button type="button" class="btn btn-secondary" data-bs-dismiss="modal">Close</button> <button type="button" class="btn btn-primary copy-to-clipboard" data-selector="bibtex-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></button> </div> </div> </div> </div> </section> <section class="abstract"> <h2>Abstract</h2> <pre class="content" style="white-space: -moz-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word; white-space: pre-wrap;">Morphisms are widely studied combinatorial objects that can be used for generating infinite families of words. In the context of Information theory, injective morphisms are called (variable length) codes. In Data compression, the morphisms, combined with parsing techniques, have been recently used to define new mechanisms to generate repetitive words. Here, we show that the repetitiveness induced by applying a morphism to a word can be captured by a compression scheme based on the Burrows-Wheeler Transform (BWT). In fact, we prove that, differently from other compression-based repetitiveness measures, the measure r_bwt (which counts the number of equal-letter runs produced by applying BWT to a word) strongly depends on the applied morphism. More in detail, we characterize the binary morphisms that preserve the value of r_bwt(w), when applied to any binary word w containing both letters. They are precisely the Sturmian morphisms, which are well-known objects in Combinatorics on words. Moreover, we prove that it is always possible to find a binary morphism that, when applied to any binary word containing both letters, increases the number of BWT-equal letter runs by a given (even) number. In addition, we derive a method for constructing arbitrarily large families of binary words on which BWT produces a given (even) number of new equal-letter runs. Such results are obtained by using a new class of morphisms that we call Thue-Morse-like. Finally, we show that there exist binary morphisms μ for which it is possible to find words w such that the difference r_bwt(μ(w))-r_bwt(w) is arbitrarily large.</pre> </section> <section class="subject-classifications mt-3"> <h2>Subject Classification</h2> <div class="acm-subject-classifications"> <h5>ACM Subject Classification</h5> <div class="content"> <ul> <li>Mathematics of computing → Combinatorics on words</li> <li>Theory of computation → Data compression</li> </ul> </div> </div> <div class="keywords "> <h5>Keywords</h5> <div class="content"> <ul class="list-style-comma"> <li>Morphism</li> <li>Burrows-Wheeler transform</li> <li>Sturmian word</li> <li>Sturmian morphism</li> <li>Thue-Morse morphism</li> <li>Repetitiveness measure</li> </ul> </div> </div> </section> <section class="metrics mt-3"> <h2>Metrics</h2> <div class="content"> <ul> <li> <a href="#" class="btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.10" data-title="On the Impact of Morphisms on BWT-Runs"> <i class="bi bi-graph-up"></i> Access Statistics </a> </li> <li> Total Accesses (updated on a weekly basis) <div class="stats-total"> <div class="stats total-downloads"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">PDF Downloads</div> </div> <div class="stats total-metadata-views"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">Metadata Views</div> </div> </div>  </li> </ul> </div> </section> <div class="offcanvas offcanvas-bottom" tabindex="-1" id="statistics-offcanvas" aria-labelledby="statistics-offcanvas"> <div class="offcanvas-header"> <h5 class="offcanvas-title"></h5> <button type="button" class="btn-close text-reset" data-bs-dismiss="offcanvas" aria-label="Close"></button> </div> <div class="offcanvas-body small" data-context=""> <div style="margin-top: 20vh" class="centered-loader"><div class="loader"></div></div> <iframe class="-hidden"></iframe> </div> </div> <section class="references mt-3"> <h2>References</h2> <div class="content"> <ol> <li> <span> Tooru Akagi, Mitsuru Funakoshi, and Shunsuke Inenaga. Sensitivity of string compressors and repetitiveness measures. Inf. Comput., 291:104999, 2023. <a href="https://scholar.google.com/scholar?hl=en&q=Tooru Akagi, Mitsuru Funakoshi, and Shunsuke Inenaga. Sensitivity of string compressors and repetitiveness measures. Inf. Comput., 291:104999, 2023." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Jean Berstel, Dominique Perrin, and Christophe Reutenauer. Codes and Automata, volume 129 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2010. <a href="https://scholar.google.com/scholar?hl=en&q=Jean Berstel, Dominique Perrin, and Christophe Reutenauer. Codes and Automata, volume 129 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2010." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Jean Berstel and Patrice Séébold. A characterization of sturmian morphisms. In MFCS, volume 711 of Lecture Notes in Computer Science, pages 281-290. Springer, 1993. <a href="https://scholar.google.com/scholar?hl=en&q=Jean Berstel and Patrice Séébold. A characterization of sturmian morphisms. In MFCS, volume 711 of Lecture Notes in Computer Science, pages 281-290. Springer, 1993." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Srecko Brlek, Andrea Frosini, Ilaria Mancini, Elisa Pergola, and Simone Rinaldi. Burrows-wheeler transform of words defined by morphisms. In IWOCA, volume 11638 of Lecture Notes in Computer Science, pages 393-404. Springer, 2019. <a href="https://scholar.google.com/scholar?hl=en&q=Srecko Brlek, Andrea Frosini, Ilaria Mancini, Elisa Pergola, and Simone Rinaldi. Burrows-wheeler transform of words defined by morphisms. In IWOCA, volume 11638 of Lecture Notes in Computer Science, pages 393-404. Springer, 2019." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Michael Burrows and David Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994. <a href="https://scholar.google.com/scholar?hl=en&q=Michael Burrows and David Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Julien Cassaigne. Sequences with grouped factors. In DLT, pages 211-222. Aristotle University of Thessaloniki, 1997. <a href="https://scholar.google.com/scholar?hl=en&q=Julien Cassaigne. Sequences with grouped factors. In DLT, pages 211-222. Aristotle University of Thessaloniki, 1997." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Giusi Castiglione, Antonio Restivo, and Marinella Sciortino. Circular Sturmian words and Hopcroft’s algorithm. Theor. Comput. Sci., 410(43):4372-4381, 2009. <a href="https://scholar.google.com/scholar?hl=en&q=Giusi Castiglione, Antonio Restivo, and Marinella Sciortino. Circular Sturmian words and Hopcroft’s algorithm. Theor. Comput. Sci., 410(43):4372-4381, 2009." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Wai-Fong Chuan. Sturmian morphisms and alpha-words. Theor. Comput. Sci., 225(1-2):129-148, 1999. <a href="https://scholar.google.com/scholar?hl=en&q=Wai-Fong Chuan. Sturmian morphisms and alpha-words. Theor. Comput. Sci., 225(1-2):129-148, 1999." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Sorin Constantinescu and Lucian Ilie. The lempel-ziv complexity of fixed points of morphisms. SIAM J. Discret. Math., 21(2):466-481, 2007. <a href="https://scholar.google.com/scholar?hl=en&q=Sorin Constantinescu and Lucian Ilie. The lempel-ziv complexity of fixed points of morphisms. SIAM J. Discret. Math., 21(2):466-481, 2007." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Maxime Crochemore, Thierry Lecroq, and Wojciech Rytter. 125 Problems in Text Algorithms: with Solutions. Cambridge University Press, 2021. <a href="https://scholar.google.com/scholar?hl=en&q=Maxime Crochemore, Thierry Lecroq, and Wojciech Rytter. 125 Problems in Text Algorithms: with Solutions. Cambridge University Press, 2021." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Paolo Ferragina and Giovanni Manzini. Opportunistic Data Structures with Applications. In FOCS, pages 390-398. IEEE Computer Society, 2000. <a href="https://scholar.google.com/scholar?hl=en&q=Paolo Ferragina and Giovanni Manzini. Opportunistic Data Structures with Applications. In FOCS, pages 390-398. IEEE Computer Society, 2000." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Andrea Frosini, Ilaria Mancini, Simone Rinaldi, Giuseppe Romana, and Marinella Sciortino. Logarithmic equal-letter runs for BWT of purely morphic words. In DLT, volume 13257 of Lect. Notes Comput. Sc., pages 139-151. Springer, 2022. <a href="https://scholar.google.com/scholar?hl=en&q=Andrea Frosini, Ilaria Mancini, Simone Rinaldi, Giuseppe Romana, and Marinella Sciortino. Logarithmic equal-letter runs for BWT of purely morphic words. In DLT, volume 13257 of Lect. Notes Comput. Sc., pages 139-151. Springer, 2022." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space. J. ACM, 67(1):2:1-2:54, 2020. <a href="https://scholar.google.com/scholar?hl=en&q=Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space. J. ACM, 67(1):2:1-2:54, 2020." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Nicola Prezza, Marinella Sciortino, and Anna Toffanello. Novel results on the number of runs of the burrows-wheeler-transform. In SOFSEM, volume 12607 of Lecture Notes in Computer Science, pages 249-262. Springer, 2021. <a href="https://scholar.google.com/scholar?hl=en&q=Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Nicola Prezza, Marinella Sciortino, and Anna Toffanello. Novel results on the number of runs of the burrows-wheeler-transform. In SOFSEM, volume 12607 of Lecture Notes in Computer Science, pages 249-262. Springer, 2021." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Giuseppe Romana, Marinella Sciortino, and Cristian Urbina. Bit catastrophes for the Burrows-Wheeler Transform. In DLT, volume 13911 of Lect. Notes Comput. Sc. Springer, 2023. <a href="https://scholar.google.com/scholar?hl=en&q=Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Giuseppe Romana, Marinella Sciortino, and Cristian Urbina. Bit catastrophes for the Burrows-Wheeler Transform. In DLT, volume 13911 of Lect. Notes Comput. Sc. Springer, 2023." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Dominik Kempa and Tomasz Kociumaka. Resolution of the Burrows-Wheeler Transform Conjecture. Commun. ACM, 65(6):91-98, 2022. <a href="https://scholar.google.com/scholar?hl=en&q=Dominik Kempa and Tomasz Kociumaka. Resolution of the Burrows-Wheeler Transform Conjecture. Commun. ACM, 65(6):91-98, 2022." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Takuya Kida, Tetsuya Matsumoto, Yusuke Shibata, Masayuki Takeda, Ayumi Shinohara, and Setsuo Arikawa. Collage system: a unifying framework for compressed pattern matching. Theor. Comput. Sci., 298(1):253-272, 2003. <a href="https://scholar.google.com/scholar?hl=en&q=Takuya Kida, Tetsuya Matsumoto, Yusuke Shibata, Masayuki Takeda, Ayumi Shinohara, and Setsuo Arikawa. Collage system: a unifying framework for compressed pattern matching. Theor. Comput. Sci., 298(1):253-272, 2003." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> John C. Kieffer and En-Hui Yang. Grammar-based codes: A new class of universal lossless source codes. IEEE Trans. Inf. Theory, 46(3):737-754, 2000. <a href="https://scholar.google.com/scholar?hl=en&q=John C. Kieffer and En-Hui Yang. Grammar-based codes: A new class of universal lossless source codes. IEEE Trans. Inf. Theory, 46(3):737-754, 2000." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323-350, 1977. <a href="https://scholar.google.com/scholar?hl=en&q=Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323-350, 1977." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Sebastian Kreft and Gonzalo Navarro. LZ77-Like Compression with Fast Random Access. In DCC, pages 239-248. IEEE, 2010. <a href="https://scholar.google.com/scholar?hl=en&q=Sebastian Kreft and Gonzalo Navarro. LZ77-Like Compression with Fast Random Access. In DCC, pages 239-248. IEEE, 2010." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Ben Langmead and Steven Salzberg. Fast gapped-read alignment with Bowtie 2. Nature methods, 9:357-359, March 2012. <a href="https://scholar.google.com/scholar?hl=en&q=Ben Langmead and Steven Salzberg. Fast gapped-read alignment with Bowtie 2. Nature methods, 9:357-359, March 2012." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Abraham Lempel and Jacob Ziv. On the complexity of finite sequences. IEEE Trans. Inf. Theory, 22(1):75-81, 1976. <a href="https://scholar.google.com/scholar?hl=en&q=Abraham Lempel and Jacob Ziv. On the complexity of finite sequences. IEEE Trans. Inf. Theory, 22(1):75-81, 1976." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Heng Li and Richard Durbin. Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinform., 26(5):589-595, 2010. <a href="https://scholar.google.com/scholar?hl=en&q=Heng Li and Richard Durbin. Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinform., 26(5):589-595, 2010." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> M. Lothaire. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, New York, NY, USA, 2002. <a href="https://scholar.google.com/scholar?hl=en&q=M. Lothaire. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, New York, NY, USA, 2002." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, Marinella Sciortino, and Luca Versari. Measuring the clustering effect of BWT via RLE. Theoret. Comput. Sci., 698:79-87, 2017. <a href="https://scholar.google.com/scholar?hl=en&q=Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, Marinella Sciortino, and Luca Versari. Measuring the clustering effect of BWT via RLE. Theoret. Comput. Sci., 698:79-87, 2017." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Sabrina Mantaci, Antonio Restivo, and Marinella Sciortino. Burrows-Wheeler transform and Sturmian words. Inf. Process. Lett., 86(5):241-246, 2003. URL: <a href="https://doi.org/10.1016/S0020-0190(02)00512-4">https://doi.org/10.1016/S0020-0190(02)00512-4</a>. </span> </li> <li> <span> Giovanni Manzini. An analysis of the Burrows-Wheeler transform. J. ACM, 48(3):407-430, 2001. <a href="https://scholar.google.com/scholar?hl=en&q=Giovanni Manzini. An analysis of the Burrows-Wheeler transform. J. ACM, 48(3):407-430, 2001." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Filippo Mignosi and Patrice Séébold. Morphismes sturmiens et règles de Rauzy. Journal de théorie des nombres de Bordeaux, 5(2):221-233, 1993. <a href="https://scholar.google.com/scholar?hl=en&q=Filippo Mignosi and Patrice Séébold. Morphismes sturmiens et règles de Rauzy. Journal de théorie des nombres de Bordeaux, 5(2):221-233, 1993." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Gonzalo Navarro. Indexing highly repetitive string collections, part I: Repetitiveness measures. ACM Computing Surveys, 54(2):article 29, 2021. <a href="https://scholar.google.com/scholar?hl=en&q=Gonzalo Navarro. Indexing highly repetitive string collections, part I: Repetitiveness measures. ACM Computing Surveys, 54(2):article 29, 2021." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Gonzalo Navarro. The compression power of the BWT: technical perspective. Commun. ACM, 65(6):90, 2022. <a href="https://scholar.google.com/scholar?hl=en&q=Gonzalo Navarro. The compression power of the BWT: technical perspective. Commun. ACM, 65(6):90, 2022." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Gonzalo Navarro, Carlos Ochoa, and Nicola Prezza. On the approximation ratio of ordered parsings. IEEE Trans. Inf. Theory, 67(2):1008-1026, 2021. <a href="https://scholar.google.com/scholar?hl=en&q=Gonzalo Navarro, Carlos Ochoa, and Nicola Prezza. On the approximation ratio of ordered parsings. IEEE Trans. Inf. Theory, 67(2):1008-1026, 2021." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Gonzalo Navarro and Cristian Urbina. On stricter reachable repetitiveness measures. In SPIRE, volume 12944 of Lect. Notes Comput. Sci., pages 193-206. Springer, 2021. <a href="https://scholar.google.com/scholar?hl=en&q=Gonzalo Navarro and Cristian Urbina. On stricter reachable repetitiveness measures. In SPIRE, volume 12944 of Lect. Notes Comput. Sci., pages 193-206. Springer, 2021." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Fully Dynamic Data Structure for LCE Queries in Compressed Space. In MFCS, volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), pages 72:1-72:15, 2016. <a href="https://scholar.google.com/scholar?hl=en&q=Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Fully Dynamic Data Structure for LCE Queries in Compressed Space. In MFCS, volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), pages 72:1-72:15, 2016." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Geneviève Paquin. On a generalization of Christoffel words: epichristoffel words. Theor. Comput. Sci., 410(38-40):3782-3791, 2009. URL: <a href="https://doi.org/10.1016/j.tcs.2009.05.014">https://doi.org/10.1016/j.tcs.2009.05.014</a>. </span> </li> <li> <span> Antonio Restivo and Giovanna Rosone. Balancing and clustering of words in the Burrows-Wheeler transform. Theor. Comput. Sci., 412(27):3019-3032, 2011. URL: <a href="https://doi.org/10.1016/j.tcs.2010.11.040">https://doi.org/10.1016/j.tcs.2010.11.040</a>. </span> </li> <li> <span> Grzegorz Rozenberg and Arto Salomaa. The mathematical theory of L systems. Academic press, 1980. <a href="https://scholar.google.com/scholar?hl=en&q=Grzegorz Rozenberg and Arto Salomaa. The mathematical theory of L systems. Academic press, 1980." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Marinella Sciortino and Luca Q. Zamboni. Suffix automata and standard sturmian words. In DLT, volume 4588 of Lect. Notes Comput. Sc., pages 382-398. Springer, 2007. <a href="https://scholar.google.com/scholar?hl=en&q=Marinella Sciortino and Luca Q. Zamboni. Suffix automata and standard sturmian words. In DLT, volume 4588 of Lect. Notes Comput. Sc., pages 382-398. Springer, 2007." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> James A. Storer and Thomas G. Szymanski. Data compression via textual substitution. J. ACM, !month = oct, 29(4):928-951, 1982. <a href="https://scholar.google.com/scholar?hl=en&q=James A. Storer and Thomas G. Szymanski. Data compression via textual substitution. J. ACM, !month = oct, 29(4):928-951, 1982." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> </ol> </div> </section> </div> </div> </div> </div> <span class="_feedback-button"> <i class="bi bi-question-circle"></i> <span class="text">Questions / Remarks / Feedback</span> </span> <div class="_feedback-form -hidden"> <span class="_feedback-close">X</span> <p>Feedback for Dagstuhl Publishing</p> <div> <textarea class="form-control" name="_feedback"></textarea> <input class="form-control" type="text" name="name" autocomplete="off" placeholder="Name (optional)" maxlength="60"> <input class="form-control" type="email" name="email" autocomplete="off" placeholder="Email (optional)" maxlength="60"> <br> <button class="btn btn-sm btn-default">Send</button> </div> </div> <div class="alert alert-success _feedback-success -hidden"> <span class="glyphicon glyphicon-ok"></span> <h3>Thanks for your feedback!</h3> <div>Feedback submitted</div> <button class="btn btn-white _feedback-done">OK</button> </div> <div class="alert alert-danger _feedback-error -hidden"> <span class="glyphicon glyphicon-remove"></span> <h3>Could not send message</h3> <div>Please try again later or send an <a href="mailto:publishing@dagstuhl.de">E-mail</a></div> <button class="btn btn-white _feedback-done">OK</button> </div> <a class="scroll-up-button -hidden" href="#_top-of-page"> <i class="bi bi-arrow-up-circle"></i> </a> <footer class="page-footer dark"> <div class="container"> <h5>About DROPS</h5> <p>Schloss Dagstuhl - Leibniz Center for Informatics has been operating the Dagstuhl Research Online Publication Server (short: DROPS) since 2004. DROPS enables publication of the latest research findings in a fast, uncomplicated manner, in addition to providing unimpeded, open access to them. All the requisite metadata on each publication is administered in accordance with general guidelines pertaining to online publications (cf. Dublin Core). This enables the online publications to be authorized for citation and made accessible to a wide readership on a permanent basis. Access is free of charge for readers following the open access idea which fosters unimpeded access to scientific publications. </p> <ul style="margin-top: -0.5em"> <li><a href="https://drops.dagstuhl.de/docs/about">More about DROPS</a></li> </ul> </div> <div class="container"> <div class="row"> <div class="col-lg-6"> <h5>Instructions for Authors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#author">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#author">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#author">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#author">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#author">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#author">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#author">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#author">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> <div class="col-lg-6"> <h5>Instructions for Editors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#editor">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#editor">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#editor">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#editor">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#editor">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#editor">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#editor">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#editor">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> </div> </div> </footer> <div class="copyright"> © 2023-2024 <a href="https://www.dagstuhl.de">Schloss Dagstuhl – LZI GmbH</a> <a href="https://drops.dagstuhl.de/docs/about">About DROPS</a> <a href="https://drops.dagstuhl.de/docs/imprint">Imprint</a> <a href="https://drops.dagstuhl.de/docs/privacy">Privacy</a> <a href="https://www.dagstuhl.de/en/publishing/team">Contact</a> </div> <script type="text/javascript" src="https://drops.dagstuhl.de/js/jquery-3.6.0.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/app.js?drops-core-2025-01-23.1"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/popper.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/circle-progress.js"></script> <script type="text/javascript"> $(document).ready(function() { const view = { statsServer: 'https://drops-stats.dagstuhl.de', animationStarted: false, isScrolledIntoView: function (elem) { const rect = elem.getBoundingClientRect(); const elemTop = rect.top; //const elemBottom = rect.bottom; // const elemHeight = rect.height; return (elemTop >= 0) && (elemTop <= window.innerHeight); }, progressCircle: function ($el) { $el.find('.circle').circleProgress({ value: 1, size: 80, fill: { color: '#555' }, animation: { duration: 1200 } }); }, countUp: function($el) { $el.find('.number').each(function() { const $this = $(this); const number = parseInt($this.attr('data-number')); let suffix = ''; if (number > 90000) { $this.text(Math.ceil(number/1000)+' k'); suffix = ' k'; } else if (number > 90000000) { $this.text(Math.ceil(number/1000000)+' m'); suffix = ' m'; } else { $this.text(Math.ceil(number)) } $({ Counter: 0 }).animate({ Counter: $this.text().replace(suffix, '').replace(',', '') }, { duration: 1000, easing: 'swing', step: function() { $this.text(Math.ceil(this.Counter).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",") + suffix); } }); }); }, checkVisibility: function() { const $container = $('.stats-total'); if (view.isScrolledIntoView($container[0])) { if (!view.animationStarted) { view.animationStarted = true; view.progressCircle($container); setTimeout(function() { view.countUp($container) }, 200); } } }, initialize: function() { $.ajax({ type: 'get', url: view.statsServer + '/api/external/drops2/document/10.4230/LIPIcs.CPM.2023.10/-/stats', success: function (result) { $('.total-downloads .number').attr('data-number', result.total.downloads); $('.total-metadata-views .number').attr('data-number', result.total.clicks); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); }, error: function () { $('.total-downloads .number').text(0); $('.total-metadata-views .number').text(0); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); } }); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const statistics = { statsServer: 'https://drops-stats.dagstuhl.de', showStatistics: function(e) { e.preventDefault(); const $offCanvas = $('#statistics-offcanvas'); const $iframe = $offCanvas.find('iframe'); const $loader = $offCanvas.find('.centered-loader'); $iframe.addClass('-hidden'); $loader.removeClass('-hidden'); $iframe[0].onload = function () { $iframe.removeClass('-hidden'); $loader.addClass('-hidden'); }.bind(this); const modeParameter = ''; const $target = $(e.currentTarget); const entityId = $target.attr('data-entity'); const title = $target.attr('data-title'); const embedUrl = statistics.statsServer + '/embed/external/drops2/' + entityId + modeParameter; let context = $offCanvas.find('.offcanvas-body').attr('data-context'); if (context === title) { context = ''; } if (context !== '') { context += '<br>'; } $offCanvas.find('.offcanvas-title').html(context + '<h2 style="font-weight: bold">' + title + '</h2>'); $offCanvas.offcanvas('show'); $offCanvas.find('iframe').attr('src', embedUrl); return false; }, initialize: function() { $('.btn-statistics').on('click', this.showStatistics); } }; statistics.initialize(); }); </script> <script type="text/javascript"> function _enableFeedback() { var $feedbackButton = $('._feedback-button, .fixed-beta-button'); var $feedbackClose = $('._feedback-close'); var $feedbackForm = $('._feedback-form'); var $feedbackSubmit = $('._feedback-form button'); var $textarea = $feedbackForm.find('textarea'); var $feedbackSuccess = $('._feedback-success'); var $feedbackError = $('._feedback-error'); var $feedbackDoneButton = $('._feedback-done'); $feedbackButton.addClass('_show'); $feedbackButton.on('click', function () { $feedbackButton.addClass('-hidden'); $feedbackForm.removeClass('-hidden'); $textarea.focus(); }); $feedbackClose.on('click', function () { $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackDoneButton.on('click', function () { $feedbackError.addClass('-hidden'); $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackSubmit.on('click', function () { var message = $textarea.val(); if (message === undefined) { message = ''; } if (message.trim() !== '') { $.ajax({ url: '/api/v1/feedback', type: 'post', data: { content: message, context: window.location.href, name: $('input[name="name"]').val(), email: $('input[name="email"]').val(), }, success: function (result) { if (result === 'success') { $textarea.val(''); $feedbackSuccess.removeClass('-hidden'); } else { $feedbackError.removeClass('-hidden'); } }, error: function () { $feedbackError.removeClass('-hidden'); } }); } }); } var _defer_counter = 0; function _defer(method) { if (window.jQuery) { method(); } else { if (_defer_counter < 20) { setTimeout(function () { _defer(method); console.log(_defer_counter); _defer_counter++; }, 500); } } } setTimeout(function() { _defer(_enableFeedback); }, 1000); </script> <script type="text/javascript"> $(document).ready(function() { const app = { maxScrollPos: window.innerWidth < 500 ? 100 // mobile : 400, // desktop $el : { navbarSearch: $('nav .navbar-search'), fixedSearchButton: $('.fixed-search-button'), copyToClipboard: $('.copy-to-clipboard') }, methods: { hideMenuOnScroll: function(scrollPos) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); if (scrollPos > app.maxScrollPos) { $menu.addClass('-hide'); $banner.addClass('-hide'); $stickySearch.addClass('-top'); $fixedSearchButton.addClass('-show'); } else { app.methods.showMenu(null, false); } }, showMenu: function(e, focus) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); $menu.removeClass('-hide'); $banner.removeClass('-hide'); $stickySearch.removeClass('-top'); $fixedSearchButton.removeClass('-show'); if (focus !== false) { $('.navbar-search').find('input[name="term"]').focus(); } }, showUpLinkOnScroll: function(scrollPos) { const $upLink = $('.scroll-up-button'); if (scrollPos > app.maxScrollPos) { $upLink.removeClass('-hidden'); } else { $upLink.addClass('-hidden'); } }, scrollHandler: function() { const scrollPos = $(document).scrollTop(); app.methods.hideMenuOnScroll(scrollPos); app.methods.showUpLinkOnScroll(scrollPos); }, copyToClipboard: function(e) { e.preventDefault(); const $current = $(e.currentTarget); // console.log($current.attr('data-selector')); const element = $('#'+$current.attr('data-selector'))[0]; console.log(element); element.select(); document.execCommand("copy"); const $success = $current.find('.bi-check'); $success.removeClass('-hidden'); setTimeout(function() { $success.addClass('-hidden'); }, 1000); }, initTooltips: function() { const tooltipTriggerList = [].slice.call(document.querySelectorAll('[data-bs-toggle="tooltip"]')) const tooltipList = tooltipTriggerList.map(function (tooltipTriggerEl) { return new bootstrap.Tooltip(tooltipTriggerEl) }); }, expandSearch: function() { app.$el.navbarSearch.addClass('expanded'); }, collapseSearch: function(e) { if (!$(e.currentTarget).is('button.btn-outline-success')) { app.$el.navbarSearch.removeClass('expanded'); } }, initDeepLinksTabs: function() { app.methods.initTabLinks(); const innerAnchors =[]; $('.tab-pane').find('[id]').each(function() { innerAnchors.push(this.getAttribute('id')); }); const anchors = []; $('a[role="tab"]').each(function() { anchors.push($(this).attr('aria-controls')); }); innerAnchors.forEach(function(anchor) { if ($('#'+anchor).length > 0) { anchors.push(anchor); } }); if (anchors.length === 0) { return; } let selectedAnchor = window.location.hash.substring(1); if (anchors.indexOf(selectedAnchor) === -1) { $('#publications-tab').tab('show'); window.scrollTo(0,0); return; } if (selectedAnchor !== 'publications') { const innerAnchorIndex = innerAnchors.indexOf(selectedAnchor); // anchor sits inside tab -> open the tab first, then scroll to anchor if (innerAnchorIndex > -1) { const $tab = $('#'+selectedAnchor).closest('.tab-pane'); console.log($tab); try { $('#'+$tab.attr('id')+'-tab').tab('show'); } catch (e) { } setTimeout(function () { $('#' + selectedAnchor)[0].scrollIntoView(); }, 800); } else { try { $('#' + selectedAnchor + '-tab').tab('show'); } catch (e) { } window.scrollTo(0, 0); } } }, initTabLinks: function() { $('[data-tab-link]').on('click', function(e) { e.preventDefault(); const $target = $(e.currentTarget); document.location.href = $target.attr('href'); document.location.reload(); }); }, }, initialize: function() { $(window).on('scroll', app.methods.scrollHandler); $(window).on('scroll-to-top', function() { window.scrollTo(0,0) }); $(document).trigger('scroll'); // set correct status for scroll-related parts (navbar/back-to-top) on page reload app.$el.copyToClipboard.on('click', app.methods.copyToClipboard); app.$el.fixedSearchButton.on('click', app.methods.showMenu); app.$el.navbarSearch.find('input').on('click', app.methods.expandSearch) app.$el.navbarSearch.find('input').on('blur', app.methods.collapseSearch); app.methods.initTooltips(); app.methods.initDeepLinksTabs(); } }; app.initialize(); }); </script> </body> </html>

CINXE.COM

On the Impact of Morphisms on BWT-Runs