34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)

<!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="JNTGSsaX3X5w5AwtYijCHC3a8xB2PNPDFjDgHcxk" /> <link rel="canonical" href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259" /> <title>34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)</title> <link rel="icon" href="https://drops.dagstuhl.de/favicon.ico" /> <link rel="stylesheet" href="https://drops.dagstuhl.de/css/app.css?drops-core-2024-10-22" /> </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"> <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"> <a class="nav-link" href="https://drops.dagstuhl.de/docs/about" id="navbarAbout"> <i class="bi bi-info-circle large-icon"></i><span class="nav-text-about-drops"> About DROPS</span> </a> </li> </ul> <form class="navbar-search d-flex" action="https://drops.dagstuhl.de/search" method="post"> <input type="hidden" name="_token" value="JNTGSsaX3X5w5AwtYijCHC3a8xB2PNPDFjDgHcxk" 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-2024-10-22" class="container "> <div id="_top-of-page"></div> <div class="fixed-search-button"><i class="bi bi-search"></i></div> <div class="volume-portal"> <br> <div class="entity-type volume"> <div> <span class="entity-type-name"> <i class="bi bi-book-half"></i> Volume </span> <span class="sharing-section"> <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/volume/LIPIcs-volume-259/metadata/xml"> Export XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259/metadata/acm-xml"> Export ACM-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259/metadata/doaj-xml"> Export DOAJ-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259/metadata/schema-org"> Export Schema.org </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259/metadata/bibtex"> Export BibTeX </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-259/metadata/html"> Export HTML </a> </li> </ul> </span> </span> </span> </div> </div> <hr> <div> <h4>LIPIcs, Volume 259</h4> <h1>34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)</h1> </div> <section class="volume-issue-header mb-4"> <hr/> <section class="is-part-of"> <ul> <li> <span>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="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> </ul> </section> <hr/> <div class="mt-5 row"> <div class="col-lg-3 mb-3"> <section class="thumbnail"> <img src="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/thumbnails/LIPIcs.CPM.2023/LIPIcs.CPM.2023.png" alt="Thumbnail PDF" /> </section> </div> <div class="col-lg-6"> <section class="mb-5"> <h4>Event</h4> <a href="https://cpm2023.u-pem.fr"> CPM 2023, June 26-28, 2023, Marne-la-Vallée, France </a> </section> <section class="editors mb-5"> <h4>Editors</h4> <div class="author person-details"> <div> <span class="name"><b>Laurent Bulteau</b></span> <a href="https://orcid.org/0000-0003-1645-9345"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:laurent.bulteau@univ-eiffel.fr"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Bulteau, Laurent"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">LIGM, CNRS, Université Gustave Eiffel, Marne-la-vallée, France</li> </ul> </div> <div class="author person-details"> <div> <span class="name"><b>Zsuzsanna Lipták</b></span> <a href="https://orcid.org/0000-0002-3233-0691"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:zsuzsanna.liptak@univr.it"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Lipták, Zsuzsanna"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">University of Verona, Italy</li> </ul> </div> </section> </div> <div class="col-lg-3"> <section class="mb-5"> <h4>Publication Details</h4> <ul> <li>published at: 2023-06-21</li> <li>Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik</li> <li>ISBN: 978-3-95977-276-1</li> <li>DBLP: <a href="https://dblp.org/db/conf/cpm/cpm2023"> db/conf/cpm/cpm2023 </a> </li> </ul> </section> <br> <section> <h4>Access Numbers</h4> <ul> <li> <a href="#" class="btn-statistics" data-entity="volume/LIPIcs-volume-259" data-title="34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)"> <i class="bi bi-graph-up"></i> Detailed Access Statistics available here </a> </li> <li> Total Document 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> </section> </div> </div> <div id="end-of-header"></div> </section> <div class="row mt-2"> <div class="col-sm-9 mt-2"> <h2>Documents <span class="btn badge color-dark _filter-info"></span></h2> <div class="documents"> <div class="no-results alert alert-danger -hidden"> No documents found matching your filter selection. </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="category">Complete Volume</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023">DOI: 10.4230/LIPIcs.CPM.2023</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023/LIPIcs.CPM.2023.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18129" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18129" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023" data-bs-toggle="tooltip" data-title="LIPIcs, Volume 259, CPM 2023, Complete Volume" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Bulteau, Laurent"></span> <span data-key="dagstuhl.contributor.author" data-value="Lipták, Zsuzsanna"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Design and analysis of algorithms"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data compression"></span> <span data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Discrete mathematics"></span> <span data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Combinatorics on words"></span> <span data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Combinatoric problems"></span> <span data-key="dagstuhl.subject.classification" data-value="Applied computing → Computational biology"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023"> LIPIcs, Volume 259, CPM 2023, Complete Volume </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Laurent Bulteau and Zsuzsanna Lipták </p> <div class="row"> <div class="collapse" id="abstract-18129"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18129">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> LIPIcs, Volume 259, CPM 2023, Complete Volume </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18129"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18129">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 1-472, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18129-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></a><br/><br/> <pre class="bibtex">@Proceedings{bulteau_et_al:LIPIcs.CPM.2023, title = {{LIPIcs, Volume 259, CPM 2023, Complete Volume}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {1--472}, 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}, URN = {urn:nbn:de:0030-drops-179536}, doi = {10.4230/LIPIcs.CPM.2023}, annote = {Keywords: LIPIcs, Volume 259, CPM 2023, Complete Volume} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18129-input">@Proceedings{bulteau_et_al:LIPIcs.CPM.2023, title = {{LIPIcs, Volume 259, CPM 2023, Complete Volume}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {1--472}, 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}, URN = {urn:nbn:de:0030-drops-179536}, doi = {10.4230/LIPIcs.CPM.2023}, annote = {Keywords: LIPIcs, Volume 259, CPM 2023, Complete Volume} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.0"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="category">Front Matter</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.0">DOI: 10.4230/LIPIcs.CPM.2023.0</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.0/LIPIcs.CPM.2023.0.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.0" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18130" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18130" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.0" data-bs-toggle="tooltip" data-title="Front Matter, Table of Contents, Preface, Conference Organization" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Bulteau, Laurent"></span> <span data-key="dagstuhl.contributor.author" data-value="Lipták, Zsuzsanna"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Design and analysis of algorithms"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data compression"></span> <span data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Discrete mathematics"></span> <span data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Combinatorics on words"></span> <span data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Combinatoric problems"></span> <span data-key="dagstuhl.subject.classification" data-value="Applied computing → Computational biology"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.0"> Front Matter, Table of Contents, Preface, Conference Organization </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Laurent Bulteau and Zsuzsanna Lipták </p> <div class="row"> <div class="collapse" id="abstract-18130"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18130">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Front Matter, Table of Contents, Preface, Conference Organization </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18130"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18130">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18130-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></a><br/><br/> <pre class="bibtex">@InProceedings{bulteau_et_al:LIPIcs.CPM.2023.0, author = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {0:i--0:xvi}, 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.0}, URN = {urn:nbn:de:0030-drops-179542}, doi = {10.4230/LIPIcs.CPM.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18130-input">@InProceedings{bulteau_et_al:LIPIcs.CPM.2023.0, author = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {0:i--0:xvi}, 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.0}, URN = {urn:nbn:de:0030-drops-179542}, doi = {10.4230/LIPIcs.CPM.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.1"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.1">DOI: 10.4230/LIPIcs.CPM.2023.1</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.1/LIPIcs.CPM.2023.1.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.1" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18131" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18131" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.1" data-bs-toggle="tooltip" data-title="Trie-Compressed Adaptive Set Intersection" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Arroyuelo, Diego"></span> <span data-key="dagstuhl.contributor.author" data-value="Castillo, Juan Pablo"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data compression"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Design and analysis of algorithms"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data structures and algorithms for data management"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems → Information retrieval query processing"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.1"> Trie-Compressed Adaptive Set Intersection </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Diego Arroyuelo and Juan Pablo Castillo </p> <div class="row"> <div class="collapse" id="abstract-18131"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18131">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> We introduce space- and time-efficient algorithms and data structures for the offline set intersection problem. We show that a sorted integer set S ⊆ [0..u) of n elements can be represented using compressed space while supporting k-way intersections in adaptive O(kδlg(u/δ)) time, δ being the alternation measure introduced by Barbay and Kenyon. Our experimental results suggest that our approaches are competitive in practice, outperforming the most efficient alternatives (Partitioned Elias-Fano indexes, Roaring Bitmaps, and Recursive Universe Partitioning (RUP)) in several scenarios, offering in general relevant space-time trade-offs. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18131"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18131">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Diego Arroyuelo and Juan Pablo Castillo. Trie-Compressed Adaptive Set Intersection. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18131-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></a><br/><br/> <pre class="bibtex">@InProceedings{arroyuelo_et_al:LIPIcs.CPM.2023.1, author = {Arroyuelo, Diego and Castillo, Juan Pablo}, title = {{Trie-Compressed Adaptive Set Intersection}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {1:1--1:19}, 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.1}, URN = {urn:nbn:de:0030-drops-179552}, doi = {10.4230/LIPIcs.CPM.2023.1}, annote = {Keywords: Set intersection problem, Adaptive Algorithms, Compressed and compact data structures} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18131-input">@InProceedings{arroyuelo_et_al:LIPIcs.CPM.2023.1, author = {Arroyuelo, Diego and Castillo, Juan Pablo}, title = {{Trie-Compressed Adaptive Set Intersection}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {1:1--1:19}, 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.1}, URN = {urn:nbn:de:0030-drops-179552}, doi = {10.4230/LIPIcs.CPM.2023.1}, annote = {Keywords: Set intersection problem, Adaptive Algorithms, Compressed and compact data structures} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.2"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.2">DOI: 10.4230/LIPIcs.CPM.2023.2</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.2/LIPIcs.CPM.2023.2.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.2" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18132" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18132" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.2" data-bs-toggle="tooltip" data-title="Approximation Algorithms for the Longest Run Subsequence Problem" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Asahiro, Yuichi"></span> <span data-key="dagstuhl.contributor.author" data-value="Eto, Hiroshi"></span> <span data-key="dagstuhl.contributor.author" data-value="Gong, Mingyang"></span> <span data-key="dagstuhl.contributor.author" data-value="Jansson, Jesper"></span> <span data-key="dagstuhl.contributor.author" data-value="Lin, Guohui"></span> <span data-key="dagstuhl.contributor.author" data-value="Miyano, Eiji"></span> <span data-key="dagstuhl.contributor.author" data-value="Ono, Hirotaka"></span> <span data-key="dagstuhl.contributor.author" data-value="Tanaka, Shunichi"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Design and analysis of algorithms"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.2"> Approximation Algorithms for the Longest Run Subsequence Problem </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka </p> <div class="row"> <div class="collapse" id="abstract-18132"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18132">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s_1 ⋯ s_n over an alphabet Σ, a run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S' of S is a sequence in which every symbol σ ∈ Σ occurs in at most one run. Given a string S, the goal of LRS is to find a longest run subsequence S^* of S such that the length |S^*| is maximized over all the run subsequences of S. It is known that LRS is APX-hard even if each symbol has at most two occurrences in the input string, and that LRS admits a polynomial-time k-approximation algorithm if the number of occurrences of every symbol in the input string is bounded by k. In this paper, we design a polynomial-time (k+1)/2-approximation algorithm for LRS under the k-occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 3/2 to 4/3. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18132"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18132">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka. Approximation Algorithms for the Longest Run Subsequence Problem. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18132-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></a><br/><br/> <pre class="bibtex">@InProceedings{asahiro_et_al:LIPIcs.CPM.2023.2, author = {Asahiro, Yuichi and Eto, Hiroshi and Gong, Mingyang and Jansson, Jesper and Lin, Guohui and Miyano, Eiji and Ono, Hirotaka and Tanaka, Shunichi}, title = {{Approximation Algorithms for the Longest Run Subsequence Problem}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {2:1--2:12}, 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.2}, URN = {urn:nbn:de:0030-drops-179560}, doi = {10.4230/LIPIcs.CPM.2023.2}, annote = {Keywords: Longest run subsequence problem, bounded occurrence, approximation algorithm} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18132-input">@InProceedings{asahiro_et_al:LIPIcs.CPM.2023.2, author = {Asahiro, Yuichi and Eto, Hiroshi and Gong, Mingyang and Jansson, Jesper and Lin, Guohui and Miyano, Eiji and Ono, Hirotaka and Tanaka, Shunichi}, title = {{Approximation Algorithms for the Longest Run Subsequence Problem}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {2:1--2:12}, 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.2}, URN = {urn:nbn:de:0030-drops-179560}, doi = {10.4230/LIPIcs.CPM.2023.2}, annote = {Keywords: Longest run subsequence problem, bounded occurrence, approximation algorithm} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.3"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.3">DOI: 10.4230/LIPIcs.CPM.2023.3</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.3/LIPIcs.CPM.2023.3.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.3" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18133" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18133" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.3" data-bs-toggle="tooltip" data-title="Optimal LZ-End Parsing Is Hard" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Bannai, Hideo"></span> <span data-key="dagstuhl.contributor.author" data-value="Funakoshi, Mitsuru"></span> <span data-key="dagstuhl.contributor.author" data-value="Kurita, Kazuhiro"></span> <span data-key="dagstuhl.contributor.author" data-value="Nakashima, Yuto"></span> <span data-key="dagstuhl.contributor.author" data-value="Seto, Kazuhisa"></span> <span data-key="dagstuhl.contributor.author" data-value="Uno, Takeaki"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data compression"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.3"> Optimal LZ-End Parsing Is Hard </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, and Takeaki Uno </p> <div class="row"> <div class="collapse" id="abstract-18133"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18133">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> LZ-End is a variant of the well-known Lempel-Ziv parsing family such that each phrase of the parsing has a previous occurrence, with the additional constraint that the previous occurrence must end at the end of a previous phrase. LZ-End was initially proposed as a greedy parsing, where each phrase is determined greedily from left to right, as the longest factor that satisfies the above constraint [Kreft & Navarro, 2010]. In this work, we consider an optimal LZ-End parsing that has the minimum number of phrases in such parsings. We show that a decision version of computing the optimal LZ-End parsing is NP-complete by showing a reduction from the vertex cover problem. Moreover, we give a MAX-SAT formulation for the optimal LZ-End parsing adapting an approach for computing various NP-hard repetitiveness measures recently presented by [Bannai et al., 2022]. We also consider the approximation ratio of the size of greedy LZ-End parsing to the size of the optimal LZ-End parsing, and give a lower bound of the ratio which asymptotically approaches 2. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18133"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18133">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, and Takeaki Uno. Optimal LZ-End Parsing Is Hard. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18133-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></a><br/><br/> <pre class="bibtex">@InProceedings{bannai_et_al:LIPIcs.CPM.2023.3, author = {Bannai, Hideo and Funakoshi, Mitsuru and Kurita, Kazuhiro and Nakashima, Yuto and Seto, Kazuhisa and Uno, Takeaki}, title = {{Optimal LZ-End Parsing Is Hard}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {3:1--3:11}, 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.3}, URN = {urn:nbn:de:0030-drops-179571}, doi = {10.4230/LIPIcs.CPM.2023.3}, annote = {Keywords: Data Compression, LZ-End, Repetitiveness measures} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18133-input">@InProceedings{bannai_et_al:LIPIcs.CPM.2023.3, author = {Bannai, Hideo and Funakoshi, Mitsuru and Kurita, Kazuhiro and Nakashima, Yuto and Seto, Kazuhisa and Uno, Takeaki}, title = {{Optimal LZ-End Parsing Is Hard}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {3:1--3:11}, 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.3}, URN = {urn:nbn:de:0030-drops-179571}, doi = {10.4230/LIPIcs.CPM.2023.3}, annote = {Keywords: Data Compression, LZ-End, Repetitiveness measures} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.4"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.4">DOI: 10.4230/LIPIcs.CPM.2023.4</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.4/LIPIcs.CPM.2023.4.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.4" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18134" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18134" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.4" data-bs-toggle="tooltip" data-title="Sliding Window String Indexing in Streams" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Bille, Philip"></span> <span data-key="dagstuhl.contributor.author" data-value="Fischer, Johannes"></span> <span data-key="dagstuhl.contributor.author" data-value="Gørtz, Inge Li"></span> <span data-key="dagstuhl.contributor.author" data-value="Pedersen, Max Rishøj"></span> <span data-key="dagstuhl.contributor.author" data-value="Stordalen, Tord Joakim"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data structures design and analysis"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.4"> Sliding Window String Indexing in Streams </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Philip Bille, Johannes Fischer, Inge Li Gørtz, Max Rishøj Pedersen, and Tord Joakim Stordalen </p> <div class="row"> <div class="collapse" id="abstract-18134"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18134">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Given a string S over an alphabet Σ, the string indexing problem is to preprocess S to subsequently support efficient pattern matching queries, that is, given a pattern string P report all the occurrences of P in S. In this paper we study the streaming sliding window string indexing problem. Here the string S arrives as a stream, one character at a time, and the goal is to maintain an index of the last w characters, called the window, for a specified parameter w. At any point in time a pattern matching query for a pattern P may arrive, also streamed one character at a time, and all occurrences of P within the current window must be returned. The streaming sliding window string indexing problem naturally captures scenarios where we want to index the most recent data (i.e. the window) of a stream while supporting efficient pattern matching. Our main result is a simple O(w) space data structure that uses O(log w) time with high probability to process each character from both the input string S and any pattern string P. Reporting each occurrence of P uses additional constant time per reported occurrence. Compared to previous work in similar scenarios this result is the first to achieve an efficient worst-case time per character from the input stream with high probability. We also consider a delayed variant of the problem, where a query may be answered at any point within the next δ characters that arrive from either stream. We present an O(w + δ) space data structure for this problem that improves the above time bounds to O(log (w/δ)). In particular, for a delay of δ = ε w we obtain an O(w) space data structure with constant time processing per character. The key idea to achieve our result is a novel and simple hierarchical structure of suffix trees of independent interest, inspired by the classic log-structured merge trees. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18134"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18134">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Philip Bille, Johannes Fischer, Inge Li Gørtz, Max Rishøj Pedersen, and Tord Joakim Stordalen. Sliding Window String Indexing in Streams. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18134-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></a><br/><br/> <pre class="bibtex">@InProceedings{bille_et_al:LIPIcs.CPM.2023.4, author = {Bille, Philip and Fischer, Johannes and G{\o}rtz, Inge Li and Pedersen, Max Rish{\o}j and Stordalen, Tord Joakim}, title = {{Sliding Window String Indexing in Streams}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {4:1--4: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.4}, URN = {urn:nbn:de:0030-drops-179587}, doi = {10.4230/LIPIcs.CPM.2023.4}, annote = {Keywords: String indexing, pattern matching, sliding window, streaming} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18134-input">@InProceedings{bille_et_al:LIPIcs.CPM.2023.4, author = {Bille, Philip and Fischer, Johannes and G{\o}rtz, Inge Li and Pedersen, Max Rish{\o}j and Stordalen, Tord Joakim}, title = {{Sliding Window String Indexing in Streams}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {4:1--4: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.4}, URN = {urn:nbn:de:0030-drops-179587}, doi = {10.4230/LIPIcs.CPM.2023.4}, annote = {Keywords: String indexing, pattern matching, sliding window, streaming} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.5"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.5">DOI: 10.4230/LIPIcs.CPM.2023.5</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.5/LIPIcs.CPM.2023.5.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.5" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18135" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18135" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.5" data-bs-toggle="tooltip" data-title="Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Boneh, Itai"></span> <span data-key="dagstuhl.contributor.author" data-value="Fried, Dvir"></span> <span data-key="dagstuhl.contributor.author" data-value="Miclăuş, Adrian"></span> <span data-key="dagstuhl.contributor.author" data-value="Popa, Alexandru"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.5"> Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Itai Boneh, Dvir Fried, Adrian Miclăuş, and Alexandru Popa </p> <div class="row"> <div class="collapse" id="abstract-18135"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18135">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Hairpin completion is an operation on formal languages that has been inspired by hairpin formation in DNA biochemistry and has many applications especially in DNA computing. Consider s to be a string over the alphabet {A, C, G, T} such that a prefix/suffix of it matches the reversed complement of a substring of s. Then, in a hairpin completion operation the reversed complement of this prefix/suffix is added to the start/end of s forming a new string. In this paper we study two problems related to the hairpin completion. The first problem asks the minimum number of hairpin operations necessary to transform one string into another, number that is called the hairpin completion distance. For this problem we show an algorithm of running time O(n²), where n is the maximum length of the two strings. Our algorithm improves on the algorithm of Manea (TCS 2010), that has running time O(n² log n). In the minimum distance common hairpin completion ancestor problem we want to find, for two input strings x and y, a string w that minimizes the sum of the hairpin completion distances to x and y. Similarly, we present an algorithm with running time O(n²) that improves by a O(log n) factor the algorithm of Manea (TCS 2010). </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18135"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18135">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Itai Boneh, Dvir Fried, Adrian Miclăuş, and Alexandru Popa. Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18135-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></a><br/><br/> <pre class="bibtex">@InProceedings{boneh_et_al:LIPIcs.CPM.2023.5, author = {Boneh, Itai and Fried, Dvir and Micl\u{a}u\c{s}, Adrian and Popa, Alexandru}, title = {{Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {5:1--5: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.5}, URN = {urn:nbn:de:0030-drops-179592}, doi = {10.4230/LIPIcs.CPM.2023.5}, annote = {Keywords: dynamic programming, incremental trees, exact algorithm} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18135-input">@InProceedings{boneh_et_al:LIPIcs.CPM.2023.5, author = {Boneh, Itai and Fried, Dvir and Micl\u{a}u\c{s}, Adrian and Popa, Alexandru}, title = {{Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {5:1--5: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.5}, URN = {urn:nbn:de:0030-drops-179592}, doi = {10.4230/LIPIcs.CPM.2023.5}, annote = {Keywords: dynamic programming, incremental trees, exact algorithm} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.6"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.6">DOI: 10.4230/LIPIcs.CPM.2023.6</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.6/LIPIcs.CPM.2023.6.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.6" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18136" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18136" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.6" data-bs-toggle="tooltip" data-title="On Distances Between Words with Parameters" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Bourhis, Pierre"></span> <span data-key="dagstuhl.contributor.author" data-value="Boussidan, Aaron"></span> <span data-key="dagstuhl.contributor.author" data-value="Gambette, Philippe"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.6"> On Distances Between Words with Parameters </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Pierre Bourhis, Aaron Boussidan, and Philippe Gambette </p> <div class="row"> <div class="collapse" id="abstract-18136"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18136">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> The edit distance between parameterized words is a generalization of the classical edit distance where it is allowed to map particular letters of the first word, called parameters, to parameters of the second word before computing the distance. This problem has been introduced in particular for detection of code duplication, and the notion of words with parameters has also been used with different semantics in other fields. The complexity of several variants of edit distances between parameterized words has been studied, however, the complexity of the most natural one, the Levenshtein distance, remained open. In this paper, we solve this open question and close the exhaustive analysis of all cases of parameterized word matching and function matching, showing that these problems are np-complete. To this aim, we also provide a comparison of the different problems, exhibiting several equivalences between them. We also provide and implement a MaxSAT encoding of the problem, as well as a simple FPT algorithm in the alphabet size, and study their efficiency on real data in the context of theater play structure comparison. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18136"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18136">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Pierre Bourhis, Aaron Boussidan, and Philippe Gambette. On Distances Between Words with Parameters. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18136-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></a><br/><br/> <pre class="bibtex">@InProceedings{bourhis_et_al:LIPIcs.CPM.2023.6, author = {Bourhis, Pierre and Boussidan, Aaron and Gambette, Philippe}, title = {{On Distances Between Words with Parameters}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {6:1--6:23}, 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.6}, URN = {urn:nbn:de:0030-drops-179602}, doi = {10.4230/LIPIcs.CPM.2023.6}, annote = {Keywords: String matching, edit distance, Levenshtein, parameterized matching, parameterized words, parameter words, instantiable words, NP-completeness, MAX-SAT} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18136-input">@InProceedings{bourhis_et_al:LIPIcs.CPM.2023.6, author = {Bourhis, Pierre and Boussidan, Aaron and Gambette, Philippe}, title = {{On Distances Between Words with Parameters}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {6:1--6:23}, 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.6}, URN = {urn:nbn:de:0030-drops-179602}, doi = {10.4230/LIPIcs.CPM.2023.6}, annote = {Keywords: String matching, edit distance, Levenshtein, parameterized matching, parameterized words, parameter words, instantiable words, NP-completeness, MAX-SAT} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.7"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.7">DOI: 10.4230/LIPIcs.CPM.2023.7</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.7/LIPIcs.CPM.2023.7.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.7" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18137" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18137" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.7" data-bs-toggle="tooltip" data-title="Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Cáceres, Manuel"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Parameterized complexity and exact algorithms"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> <span data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Graph algorithms"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.7"> Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Manuel Cáceres </p> <div class="row"> <div class="collapse" id="abstract-18137"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18137">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> The problem of String Matching to Labeled Graphs (SMLG) asks to find all the paths in a labeled graph G = (V, E) whose spellings match that of an input string S ∈ Σ^m. SMLG can be solved in quadratic O(m|E|) time [Amir et al., JALG 2000], which was proven to be optimal by a recent lower bound conditioned on SETH [Equi et al., ICALP 2019]. The lower bound states that no strongly subquadratic time algorithm exists, even if restricted to directed acyclic graphs (DAGs). In this work we present the first parameterized algorithms for SMLG on DAGs. Our parameters capture the topological structure of G. All our results are derived from a generalization of the Knuth-Morris-Pratt algorithm [Park and Kim, CPM 1995] optimized to work in time proportional to the number of prefix-incomparable matches. To obtain the parameterization in the topological structure of G, we first study a special class of DAGs called funnels [Millani et al., JCO 2020] and generalize them to k-funnels and the class ST_k. We present several novel characterizations and algorithmic contributions on both funnels and their generalizations. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18137"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18137">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Manuel Cáceres. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18137-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></a><br/><br/> <pre class="bibtex">@InProceedings{caceres:LIPIcs.CPM.2023.7, author = {C\'{a}ceres, Manuel}, title = {{Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {7:1--7:19}, 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.7}, URN = {urn:nbn:de:0030-drops-179619}, doi = {10.4230/LIPIcs.CPM.2023.7}, annote = {Keywords: string matching, parameterized algorithms, FPT inside P, string algorithms, graph algorithms, directed acyclic graphs, labeled graphs, funnels} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18137-input">@InProceedings{caceres:LIPIcs.CPM.2023.7, author = {C\'{a}ceres, Manuel}, title = {{Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {7:1--7:19}, 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.7}, URN = {urn:nbn:de:0030-drops-179619}, doi = {10.4230/LIPIcs.CPM.2023.7}, annote = {Keywords: string matching, parameterized algorithms, FPT inside P, string algorithms, graph algorithms, directed acyclic graphs, labeled graphs, funnels} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.8"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.8">DOI: 10.4230/LIPIcs.CPM.2023.8</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.8/LIPIcs.CPM.2023.8.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.8" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18138" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18138" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.8" data-bs-toggle="tooltip" data-title="Optimal Near-Linear Space Heaviest Induced Ancestors" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Charalampopoulos, Panagiotis"></span> <span data-key="dagstuhl.contributor.author" data-value="Dudek, Bartłomiej"></span> <span data-key="dagstuhl.contributor.author" data-value="Gawrychowski, Paweł"></span> <span data-key="dagstuhl.contributor.author" data-value="Pokorski, Karol"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.8"> Optimal Near-Linear Space Heaviest Induced Ancestors </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Panagiotis Charalampopoulos, Bartłomiej Dudek, Paweł Gawrychowski, and Karol Pokorski </p> <div class="row"> <div class="collapse" id="abstract-18138"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18138">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> We revisit the Heaviest Induced Ancestors (HIA) problem that was introduced by Gagie, Gawrychowski, and Nekrich [CCCG 2013] and has a number of applications in string algorithms. Let T₁ and T₂ be two rooted trees whose nodes have weights that are increasing in all root-to-leaf paths, and labels on the leaves, such that no two leaves of a tree have the same label. A pair of nodes (u, v) ∈ T₁ × T₂ is induced if and only if there is a label shared by leaf-descendants of u and v. In an HIA query, given nodes x ∈ T₁ and y ∈ T₂, the goal is to find an induced pair of nodes (u, v) of the maximum total weight such that u is an ancestor of x and v is an ancestor of y. Let n be the upper bound on the sizes of the two trees. It is known that no data structure of size 𝒪̃(n) can answer HIA queries in o(log n / log log n) time [Charalampopoulos, Gawrychowski, Pokorski; ICALP 2020]. This (unconditional) lower bound is a polyloglog n factor away from the query time of the fastest 𝒪̃(n)-size data structure known to date for the HIA problem [Abedin, Hooshmand, Ganguly, Thankachan; Algorithmica 2022]. In this work, we resolve the query-time complexity of the HIA problem for the near-linear space regime by presenting a data structure that can be built in 𝒪̃(n) time and answers HIA queries in 𝒪(log n/log log n) time. As a direct corollary, we obtain an 𝒪̃(n)-size data structure that maintains the LCS of a static string and a dynamic string, both of length at most n, in time optimal for this space regime. The main ingredients of our approach are fractional cascading and the utilization of an 𝒪(log n/ log log n)-depth tree decomposition. The latter allows us to break through the Ω(log n) barrier faced by previous works, due to the depth of the considered heavy-path decompositions. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18138"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18138">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Panagiotis Charalampopoulos, Bartłomiej Dudek, Paweł Gawrychowski, and Karol Pokorski. Optimal Near-Linear Space Heaviest Induced Ancestors. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18138-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></a><br/><br/> <pre class="bibtex">@InProceedings{charalampopoulos_et_al:LIPIcs.CPM.2023.8, author = {Charalampopoulos, Panagiotis and Dudek, Bart{\l}omiej and Gawrychowski, Pawe{\l} and Pokorski, Karol}, title = {{Optimal Near-Linear Space Heaviest Induced Ancestors}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {8:1--8: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.8}, URN = {urn:nbn:de:0030-drops-179624}, doi = {10.4230/LIPIcs.CPM.2023.8}, annote = {Keywords: data structures, string algorithms, fractional cascading} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18138-input">@InProceedings{charalampopoulos_et_al:LIPIcs.CPM.2023.8, author = {Charalampopoulos, Panagiotis and Dudek, Bart{\l}omiej and Gawrychowski, Pawe{\l} and Pokorski, Karol}, title = {{Optimal Near-Linear Space Heaviest Induced Ancestors}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {8:1--8: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.8}, URN = {urn:nbn:de:0030-drops-179624}, doi = {10.4230/LIPIcs.CPM.2023.8}, annote = {Keywords: data structures, string algorithms, fractional cascading} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.9"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.9">DOI: 10.4230/LIPIcs.CPM.2023.9</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.9/LIPIcs.CPM.2023.9.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.9" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18139" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18139" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.9" data-bs-toggle="tooltip" data-title="From Bit-Parallelism to Quantum String Matching for Labelled Graphs" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Equi, Massimo"></span> <span data-key="dagstuhl.contributor.author" data-value="Meijer-van de Griend, Arianne"></span> <span data-key="dagstuhl.contributor.author" data-value="Mäkinen, Veli"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Quantum computation theory"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Parallel algorithms"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Graph algorithms analysis"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.9"> From Bit-Parallelism to Quantum String Matching for Labelled Graphs </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Massimo Equi, Arianne Meijer-van de Griend, and Veli Mäkinen </p> <div class="row"> <div class="collapse" id="abstract-18139"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18139">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor w, where w is the computer word size. A classic example is computing the edit distance of two strings of length n, which can be solved in O(n²/w) time. In a reasonable classical model of computation, one can assume w = Θ(log n), and obtaining significantly better speed-ups is unlikely in the light of conditional lower bounds obtained for such problems. In this paper, we study the connection of bit-parallelism to quantum computation, aiming to see if a bit-parallel algorithm could be converted to a quantum algorithm with better than logarithmic speed-up. We focus on string matching in labeled graphs, the problem of finding an exact occurrence of a string as the label of a path in a graph. This problem admits a quadratic conditional lower bound under a very restricted class of graphs (Equi et al. ICALP 2019), stating that no algorithm in the classical model of computation can solve the problem in time O(|P||E|^(1-ε)) or O(|P|^(1-ε)|E|). We show that a simple bit-parallel algorithm on such restricted family of graphs (level DAGs) can indeed be converted into a realistic quantum algorithm that attains subquadratic time complexity O(|E|√|P|). </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18139"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18139">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Massimo Equi, Arianne Meijer-van de Griend, and Veli Mäkinen. From Bit-Parallelism to Quantum String Matching for Labelled Graphs. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18139-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></a><br/><br/> <pre class="bibtex">@InProceedings{equi_et_al:LIPIcs.CPM.2023.9, author = {Equi, Massimo and Meijer-van de Griend, Arianne and M\"{a}kinen, Veli}, title = {{From Bit-Parallelism to Quantum String Matching for Labelled Graphs}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {9:1--9:20}, 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.9}, URN = {urn:nbn:de:0030-drops-179637}, doi = {10.4230/LIPIcs.CPM.2023.9}, annote = {Keywords: Bit-parallelism, quantum computation, string matching, level DAGs} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18139-input">@InProceedings{equi_et_al:LIPIcs.CPM.2023.9, author = {Equi, Massimo and Meijer-van de Griend, Arianne and M\"{a}kinen, Veli}, title = {{From Bit-Parallelism to Quantum String Matching for Labelled Graphs}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {9:1--9:20}, 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.9}, URN = {urn:nbn:de:0030-drops-179637}, doi = {10.4230/LIPIcs.CPM.2023.9}, annote = {Keywords: Bit-parallelism, quantum computation, string matching, level DAGs} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.10"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.10">DOI: 10.4230/LIPIcs.CPM.2023.10</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.10/LIPIcs.CPM.2023.10.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18140" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18140" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.10" data-bs-toggle="tooltip" data-title="On the Impact of Morphisms on BWT-Runs" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Fici, Gabriele"></span> <span data-key="dagstuhl.contributor.author" data-value="Romana, Giuseppe"></span> <span data-key="dagstuhl.contributor.author" data-value="Sciortino, Marinella"></span> <span data-key="dagstuhl.contributor.author" data-value="Urbina, Cristian"></span> <span data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Combinatorics on words"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data compression"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.10"> On the Impact of Morphisms on BWT-Runs </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Gabriele Fici, Giuseppe Romana, Marinella Sciortino, and Cristian Urbina </p> <div class="row"> <div class="collapse" id="abstract-18140"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18140">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> 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. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18140"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18140">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">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)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18140-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></a><br/><br/> <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> <textarea style="position: absolute; top: 200vh" id="bibtex-18140-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> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.11"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.11">DOI: 10.4230/LIPIcs.CPM.2023.11</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.11/LIPIcs.CPM.2023.11.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.11" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18141" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18141" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.11" data-bs-toggle="tooltip" data-title="Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Gabory, Esteban"></span> <span data-key="dagstuhl.contributor.author" data-value="Mwaniki, Moses Njagi"></span> <span data-key="dagstuhl.contributor.author" data-value="Pisanti, Nadia"></span> <span data-key="dagstuhl.contributor.author" data-value="Pissis, Solon P."></span> <span data-key="dagstuhl.contributor.author" data-value="Radoszewski, Jakub"></span> <span data-key="dagstuhl.contributor.author" data-value="Sweering, Michelle"></span> <span data-key="dagstuhl.contributor.author" data-value="Zuba, Wiktor"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.11"> Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Esteban Gabory, Moses Njagi Mwaniki, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski, Michelle Sweering, and Wiktor Zuba </p> <div class="row"> <div class="collapse" id="abstract-18141"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18141">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> An elastic-degenerate (ED) string T is a sequence of n sets T[1],…,T[n] containing m strings in total whose cumulative length is N. We call n, m, and N the length, the cardinality and the size of T, respectively. The language of T is defined as ℒ(T) = {S_1 ⋯ S_n : S_i ∈ T[i] for all i ∈ [1,n]}. ED strings have been introduced to represent a set of closely-related DNA sequences, also known as a pangenome. The basic question we investigate here is: Given two ED strings, how fast can we check whether the two languages they represent have a nonempty intersection? We call the underlying problem the ED String Intersection (EDSI) problem. For two ED strings T₁ and T₂ of lengths n₁ and n₂, cardinalities m₁ and m₂, and sizes N₁ and N₂, respectively, we show the following: - There is no 𝒪((N₁N₂)^{1-ε})-time algorithm, thus no 𝒪((N₁m₂+N₂m₁)^{1-ε})-time algorithm and no 𝒪((N₁n₂+N₂n₁)^{1-ε})-time algorithm, for any constant ε > 0, for EDSI even when T₁ and T₂ are over a binary alphabet, unless the Strong Exponential-Time Hypothesis is false. - There is no combinatorial 𝒪((N₁+N₂)^{1.2-ε}f(n₁,n₂))-time algorithm, for any constant ε > 0 and any function f, for EDSI even when T₁ and T₂ are over a binary alphabet, unless the Boolean Matrix Multiplication conjecture is false. - An 𝒪(N₁log N₁log n₁+N₂log N₂log n₂)-time algorithm for outputting a compact (RLE) representation of the intersection language of two unary ED strings. In the case when T₁ and T₂ are given in a compact representation, we show that the problem is NP-complete. - An 𝒪(N₁m₂+N₂m₁)-time algorithm for EDSI. - An Õ(N₁^{ω-1}n₂+N₂^{ω-1}n₁)-time algorithm for EDSI, where ω is the exponent of matrix multiplication; the Õ notation suppresses factors that are polylogarithmic in the input size. We also show that the techniques we develop have applications outside of ED string comparison. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18141"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18141">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Esteban Gabory, Moses Njagi Mwaniki, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski, Michelle Sweering, and Wiktor Zuba. Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18141-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></a><br/><br/> <pre class="bibtex">@InProceedings{gabory_et_al:LIPIcs.CPM.2023.11, author = {Gabory, Esteban and Mwaniki, Moses Njagi and Pisanti, Nadia and Pissis, Solon P. and Radoszewski, Jakub and Sweering, Michelle and Zuba, Wiktor}, title = {{Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {11:1--11:20}, 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.11}, URN = {urn:nbn:de:0030-drops-179650}, doi = {10.4230/LIPIcs.CPM.2023.11}, annote = {Keywords: elastic-degenerate string, sequence comparison, languages intersection, pangenome, acronym identification} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18141-input">@InProceedings{gabory_et_al:LIPIcs.CPM.2023.11, author = {Gabory, Esteban and Mwaniki, Moses Njagi and Pisanti, Nadia and Pissis, Solon P. and Radoszewski, Jakub and Sweering, Michelle and Zuba, Wiktor}, title = {{Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {11:1--11:20}, 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.11}, URN = {urn:nbn:de:0030-drops-179650}, doi = {10.4230/LIPIcs.CPM.2023.11}, annote = {Keywords: elastic-degenerate string, sequence comparison, languages intersection, pangenome, acronym identification} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.12"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.12">DOI: 10.4230/LIPIcs.CPM.2023.12</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.12/LIPIcs.CPM.2023.12.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.12" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18142" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18142" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.12" data-bs-toggle="tooltip" data-title="Compressed Indexing for Consecutive Occurrences" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Gawrychowski, Paweł"></span> <span data-key="dagstuhl.contributor.author" data-value="Gourdel, Garance"></span> <span data-key="dagstuhl.contributor.author" data-value="Starikovskaya, Tatiana"></span> <span data-key="dagstuhl.contributor.author" data-value="Steiner, Teresa Anna"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data compression"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.12"> Compressed Indexing for Consecutive Occurrences </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, and Teresa Anna Steiner </p> <div class="row"> <div class="collapse" id="abstract-18142"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18142">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> The fundamental question considered in algorithms on strings is that of indexing, that is, preprocessing a given string for specific queries. By now we have a number of efficient solutions for this problem when the queries ask for an exact occurrence of a given pattern P. However, practical applications motivate the necessity of considering more complex queries, for example concerning near occurrences of two patterns. Recently, Bille et al. [CPM 2021] introduced a variant of such queries, called gapped consecutive occurrences, in which a query consists of two patterns P₁ and P₂ and a range [a,b], and one must find all consecutive occurrences (q₁,q₂) of P₁ and P₂ such that q₂-q₁ ∈ [a,b]. By their results, we cannot hope for a very efficient indexing structure for such queries, even if a = 0 is fixed (although at the same time they provided a non-trivial upper bound). Motivated by this, we focus on a text given as a straight-line program (SLP) and design an index taking space polynomial in the size of the grammar that answers such queries in time optimal up to polylog factors. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18142"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18142">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, and Teresa Anna Steiner. Compressed Indexing for Consecutive Occurrences. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18142-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></a><br/><br/> <pre class="bibtex">@InProceedings{gawrychowski_et_al:LIPIcs.CPM.2023.12, author = {Gawrychowski, Pawe{\l} and Gourdel, Garance and Starikovskaya, Tatiana and Steiner, Teresa Anna}, title = {{Compressed Indexing for Consecutive Occurrences}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {12:1--12:22}, 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.12}, URN = {urn:nbn:de:0030-drops-179666}, doi = {10.4230/LIPIcs.CPM.2023.12}, annote = {Keywords: Compressed indexing, two patterns, consecutive occurrences} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18142-input">@InProceedings{gawrychowski_et_al:LIPIcs.CPM.2023.12, author = {Gawrychowski, Pawe{\l} and Gourdel, Garance and Starikovskaya, Tatiana and Steiner, Teresa Anna}, title = {{Compressed Indexing for Consecutive Occurrences}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {12:1--12:22}, 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.12}, URN = {urn:nbn:de:0030-drops-179666}, doi = {10.4230/LIPIcs.CPM.2023.12}, annote = {Keywords: Compressed indexing, two patterns, consecutive occurrences} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.13"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.13">DOI: 10.4230/LIPIcs.CPM.2023.13</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.13/LIPIcs.CPM.2023.13.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.13" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18143" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18143" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.13" data-bs-toggle="tooltip" data-title="Order-Preserving Squares in Strings" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Gawrychowski, Paweł"></span> <span data-key="dagstuhl.contributor.author" data-value="Ghazawi, Samah"></span> <span data-key="dagstuhl.contributor.author" data-value="Landau, Gad M."></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.13"> Order-Preserving Squares in Strings </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Paweł Gawrychowski, Samah Ghazawi, and Gad M. Landau </p> <div class="row"> <div class="collapse" id="abstract-18143"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18143">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> An order-preserving square in a string is a fragment of the form uv where u ≠ v and u is order-isomorphic to v. We show that a string w of length n over an alphabet of size σ contains 𝒪(σn) order-preserving squares that are distinct as words. This improves the upper bound of 𝒪(σ²n) by Kociumaka, Radoszewski, Rytter, and Waleń [TCS 2016]. Further, for every σ and n we exhibit a string with Ω(σn) order-preserving squares that are distinct as words, thus establishing that our upper bound is asymptotically tight. Finally, we design an 𝒪(σn) time algorithm that outputs all order-preserving squares that occur in a given string and are distinct as words. By our lower bound, this is optimal in the worst case. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18143"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18143">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Paweł Gawrychowski, Samah Ghazawi, and Gad M. Landau. Order-Preserving Squares in Strings. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18143-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></a><br/><br/> <pre class="bibtex">@InProceedings{gawrychowski_et_al:LIPIcs.CPM.2023.13, author = {Gawrychowski, Pawe{\l} and Ghazawi, Samah and Landau, Gad M.}, title = {{Order-Preserving Squares in Strings}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {13:1--13:19}, 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.13}, URN = {urn:nbn:de:0030-drops-179676}, doi = {10.4230/LIPIcs.CPM.2023.13}, annote = {Keywords: repetitions, distinct squares, order-isomorphism} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18143-input">@InProceedings{gawrychowski_et_al:LIPIcs.CPM.2023.13, author = {Gawrychowski, Pawe{\l} and Ghazawi, Samah and Landau, Gad M.}, title = {{Order-Preserving Squares in Strings}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {13:1--13:19}, 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.13}, URN = {urn:nbn:de:0030-drops-179676}, doi = {10.4230/LIPIcs.CPM.2023.13}, annote = {Keywords: repetitions, distinct squares, order-isomorphism} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.14"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.14">DOI: 10.4230/LIPIcs.CPM.2023.14</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.14/LIPIcs.CPM.2023.14.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.14" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18144" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18144" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.14" data-bs-toggle="tooltip" data-title="MUL-Tree Pruning for Consistency and Compatibility" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Hampson, Christopher"></span> <span data-key="dagstuhl.contributor.author" data-value="Harvey, Daniel J."></span> <span data-key="dagstuhl.contributor.author" data-value="Iliopoulos, Costas S."></span> <span data-key="dagstuhl.contributor.author" data-value="Jansson, Jesper"></span> <span data-key="dagstuhl.contributor.author" data-value="Lim, Zara"></span> <span data-key="dagstuhl.contributor.author" data-value="Sung, Wing-Kin"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.14"> MUL-Tree Pruning for Consistency and Compatibility </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Christopher Hampson, Daniel J. Harvey, Costas S. Iliopoulos, Jesper Jansson, Zara Lim, and Wing-Kin Sung </p> <div class="row"> <div class="collapse" id="abstract-18144"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18144">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> A multi-labelled tree (or MUL-tree) is a rooted tree leaf-labelled by a set of labels, where each label may appear more than once in the tree. We consider the MUL-tree Set Pruning for Consistency problem (MULSETPC), which takes as input a set of MUL-trees and asks whether there exists a perfect pruning of each MUL-tree that results in a consistent set of single-labelled trees. MULSETPC was proven to be NP-complete by Gascon et al. when the MUL-trees are binary, each leaf label is used at most three times, and the number of MUL-trees is unbounded. To determine the computational complexity of the problem when the number of MUL-trees is constant was left as an open problem. Here, we resolve this question by proving a much stronger result, namely that MULSETPC is NP-complete even when there are only two MUL-trees, every leaf label is used at most twice, and every MUL-tree is either binary or has constant height. Furthermore, we introduce an extension of MULSETPC that we call MULSETPComp, which replaces the notion of consistency with compatibility, and prove that MULSETPComp is NP-complete even when there are only two MUL-trees, every leaf label is used at most thrice, and every MUL-tree has constant height. Finally, we present a polynomial-time algorithm for instances of MULSETPC with a constant number of binary MUL-trees, in the special case where every leaf label occurs exactly once in at least one MUL-tree. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18144"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18144">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Christopher Hampson, Daniel J. Harvey, Costas S. Iliopoulos, Jesper Jansson, Zara Lim, and Wing-Kin Sung. MUL-Tree Pruning for Consistency and Compatibility. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18144-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></a><br/><br/> <pre class="bibtex">@InProceedings{hampson_et_al:LIPIcs.CPM.2023.14, author = {Hampson, Christopher and Harvey, Daniel J. and Iliopoulos, Costas S. and Jansson, Jesper and Lim, Zara and Sung, Wing-Kin}, title = {{MUL-Tree Pruning for Consistency and Compatibility}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {14:1--14: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.14}, URN = {urn:nbn:de:0030-drops-179682}, doi = {10.4230/LIPIcs.CPM.2023.14}, annote = {Keywords: multi-labelled tree, phylogenetic tree, consistent, compatible, pruning, algorithm, NP-complete} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18144-input">@InProceedings{hampson_et_al:LIPIcs.CPM.2023.14, author = {Hampson, Christopher and Harvey, Daniel J. and Iliopoulos, Costas S. and Jansson, Jesper and Lim, Zara and Sung, Wing-Kin}, title = {{MUL-Tree Pruning for Consistency and Compatibility}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {14:1--14: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.14}, URN = {urn:nbn:de:0030-drops-179682}, doi = {10.4230/LIPIcs.CPM.2023.14}, annote = {Keywords: multi-labelled tree, phylogenetic tree, consistent, compatible, pruning, algorithm, NP-complete} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.15"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.15">DOI: 10.4230/LIPIcs.CPM.2023.15</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.15/LIPIcs.CPM.2023.15.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.15" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18145" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18145" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.15" data-bs-toggle="tooltip" data-title="Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Iliopoulos, Costas S."></span> <span data-key="dagstuhl.contributor.author" data-value="Kociumaka, Tomasz"></span> <span data-key="dagstuhl.contributor.author" data-value="Radoszewski, Jakub"></span> <span data-key="dagstuhl.contributor.author" data-value="Rytter, Wojciech"></span> <span data-key="dagstuhl.contributor.author" data-value="Waleń, Tomasz"></span> <span data-key="dagstuhl.contributor.author" data-value="Zuba, Wiktor"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.15"> Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba </p> <div class="row"> <div class="collapse" id="abstract-18145"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18145">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Cyclic versions of covers and roots of a string are considered in this paper. A prefix V of a string S is a cyclic root of S if S is a concatenation of cyclic rotations of V. A prefix V of S is a cyclic cover of S if the occurrences of the cyclic rotations of V cover all positions of S. We present 𝒪(n)-time algorithms computing all cyclic roots (using number-theoretic tools) and all cyclic covers (using tools related to seeds) of a length-n string over an integer alphabet. Our results improve upon 𝒪(n log log n) and 𝒪(n log n) time complexities of recent algorithms of Grossi et al. (WALCOM 2023) for the respective problems and provide novel approaches to the problems. As a by-product, we obtain an optimal data structure for Internal Circular Pattern Matching queries that generalize Internal Pattern Matching and Cyclic Equivalence queries of Kociumaka et al. (SODA 2015). </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18145"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18145">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba. Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18145-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></a><br/><br/> <pre class="bibtex">@InProceedings{iliopoulos_et_al:LIPIcs.CPM.2023.15, author = {Iliopoulos, Costas S. and Kociumaka, Tomasz and Radoszewski, Jakub and Rytter, Wojciech and Wale\'{n}, Tomasz and Zuba, Wiktor}, title = {{Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {15:1--15:15}, 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.15}, URN = {urn:nbn:de:0030-drops-179697}, doi = {10.4230/LIPIcs.CPM.2023.15}, annote = {Keywords: cyclic cover, cyclic root, circular pattern matching, internal pattern matching} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18145-input">@InProceedings{iliopoulos_et_al:LIPIcs.CPM.2023.15, author = {Iliopoulos, Costas S. and Kociumaka, Tomasz and Radoszewski, Jakub and Rytter, Wojciech and Wale\'{n}, Tomasz and Zuba, Wiktor}, title = {{Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {15:1--15:15}, 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.15}, URN = {urn:nbn:de:0030-drops-179697}, doi = {10.4230/LIPIcs.CPM.2023.15}, annote = {Keywords: cyclic cover, cyclic root, circular pattern matching, internal pattern matching} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.16"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.16">DOI: 10.4230/LIPIcs.CPM.2023.16</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.16/LIPIcs.CPM.2023.16.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.16" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18146" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18146" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.16" data-bs-toggle="tooltip" data-title="Faster Prefix-Sorting Algorithms for Deterministic Finite Automata" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Kim, Sung-Hwan"></span> <span data-key="dagstuhl.contributor.author" data-value="Olivares, Francisco"></span> <span data-key="dagstuhl.contributor.author" data-value="Prezza, Nicola"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Formal languages and automata theory"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.16"> Faster Prefix-Sorting Algorithms for Deterministic Finite Automata </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Sung-Hwan Kim, Francisco Olivares, and Nicola Prezza </p> <div class="row"> <div class="collapse" id="abstract-18146"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18146">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Sorting is a fundamental algorithmic pre-processing technique which often allows to represent data more compactly and, at the same time, speeds up search queries on it. In this paper, we focus on the well-studied problem of sorting and indexing string sets. Since the introduction of suffix trees in 1973, dozens of suffix sorting algorithms have been described in the literature. In 2017, these techniques were extended to sets of strings described by means of finite automata: the theory of Wheeler graphs [Gagie et al., TCS'17] introduced automata whose states can be totally-sorted according to the co-lexicographic (co-lex in the following) order of the prefixes of words accepted by the automaton. More recently, in [Cotumaccio, Prezza, SODA'21] it was shown how to extend these ideas to arbitrary automata by means of partial co-lex orders. This work showed that a co-lex order of minimum width (thus optimizing search query times) on deterministic finite automata (DFAs) can be computed in O(m² + n^{5/2}) time, m being the number of transitions and n the number of states of the input DFA. In this paper, we exhibit new combinatorial properties of the minimum-width co-lex order of DFAs and exploit them to design faster prefix sorting algorithms. In particular, we describe two algorithms sorting arbitrary DFAs in O(mn) and O(n² log n) time, respectively, and an algorithm sorting acyclic DFAs in O(m log n) time. Within these running times, all algorithms compute also a smallest chain partition of the partial order (required to index the DFA). We present an experiment result to show that an optimized implementation of the O(n² log n)-time algorithm exhibits a nearly-linear behaviour on large deterministic pan-genomic graphs and is thus also of practical interest. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18146"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18146">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Sung-Hwan Kim, Francisco Olivares, and Nicola Prezza. Faster Prefix-Sorting Algorithms for Deterministic Finite Automata. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18146-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></a><br/><br/> <pre class="bibtex">@InProceedings{kim_et_al:LIPIcs.CPM.2023.16, author = {Kim, Sung-Hwan and Olivares, Francisco and Prezza, Nicola}, title = {{Faster Prefix-Sorting Algorithms for Deterministic Finite Automata}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {16:1--16:16}, 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.16}, URN = {urn:nbn:de:0030-drops-179707}, doi = {10.4230/LIPIcs.CPM.2023.16}, annote = {Keywords: String Matching, Deterministic Finite Automata, Graph Indexing, Co-lexicographical Sorting} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18146-input">@InProceedings{kim_et_al:LIPIcs.CPM.2023.16, author = {Kim, Sung-Hwan and Olivares, Francisco and Prezza, Nicola}, title = {{Faster Prefix-Sorting Algorithms for Deterministic Finite Automata}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {16:1--16:16}, 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.16}, URN = {urn:nbn:de:0030-drops-179707}, doi = {10.4230/LIPIcs.CPM.2023.16}, annote = {Keywords: String Matching, Deterministic Finite Automata, Graph Indexing, Co-lexicographical Sorting} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.17"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.17">DOI: 10.4230/LIPIcs.CPM.2023.17</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.17/LIPIcs.CPM.2023.17.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.17" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18147" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18147" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.17" data-bs-toggle="tooltip" data-title="Encoding Hard String Problems with Answer Set Programming" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Köppl, Dominik"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation"></span> <span data-key="dagstuhl.subject.classification" data-value="Computing methodologies → Artificial intelligence"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Discrete optimization"></span> <span data-key="dagstuhl.subject.classification" data-value="Hardware → Theorem proving and SAT solving"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.17"> Encoding Hard String Problems with Answer Set Programming </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Dominik Köppl </p> <div class="row"> <div class="collapse" id="abstract-18147"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18147">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Despite the simple, one-dimensional nature of strings, several computationally hard problems on strings are known. Tackling hard problems beyond sizes of toy instances with straight-forward solutions is infeasible. To solve these problems on datasets of even small sizes, effort has to be put into the conception of algorithms leveraging profound characteristics of the input. Finding these characteristics can be eased by rapidly creating and evaluating prototypes of new concepts in how to tackle hard problems. Such a rapid-prototyping method for hard problems is answer set programming (ASP). In this light, we study the application of ASP on five NP-hard optimization problems in the field of strings. We provide MAX-SAT and ASP encodings, and empirically reason about the merits and flaws when working with ASP solvers. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18147"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18147">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Dominik Köppl. Encoding Hard String Problems with Answer Set Programming. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18147-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></a><br/><br/> <pre class="bibtex">@InProceedings{koppl:LIPIcs.CPM.2023.17, author = {K\"{o}ppl, Dominik}, title = {{Encoding Hard String Problems with Answer Set Programming}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {17:1--17:21}, 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.17}, URN = {urn:nbn:de:0030-drops-179711}, doi = {10.4230/LIPIcs.CPM.2023.17}, annote = {Keywords: optimization problems, answer set programming, MAX-SAT encoding, NP-hard string problems} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18147-input">@InProceedings{koppl:LIPIcs.CPM.2023.17, author = {K\"{o}ppl, Dominik}, title = {{Encoding Hard String Problems with Answer Set Programming}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {17:1--17:21}, 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.17}, URN = {urn:nbn:de:0030-drops-179711}, doi = {10.4230/LIPIcs.CPM.2023.17}, annote = {Keywords: optimization problems, answer set programming, MAX-SAT encoding, NP-hard string problems} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.18"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.18">DOI: 10.4230/LIPIcs.CPM.2023.18</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.18/LIPIcs.CPM.2023.18.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.18" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18148" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18148" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.18" data-bs-toggle="tooltip" data-title="On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Komusiewicz, Christian"></span> <span data-key="dagstuhl.contributor.author" data-value="Linz, Simone"></span> <span data-key="dagstuhl.contributor.author" data-value="Morawietz, Nils"></span> <span data-key="dagstuhl.contributor.author" data-value="Schestag, Jannik"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Parameterized complexity and exact algorithms"></span> <span data-key="dagstuhl.subject.classification" data-value="Applied computing → Molecular evolution"></span> <span data-key="dagstuhl.subject.classification" data-value="Applied computing → Computational genomics"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.18"> On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Christian Komusiewicz, Simone Linz, Nils Morawietz, and Jannik Schestag </p> <div class="row"> <div class="collapse" id="abstract-18148"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18148">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Maximum Parsimony is the problem of computing a most parsimonious phylogenetic tree for a taxa set X from character data for X. A common strategy to attack this notoriously hard problem is to perform a local search over the phylogenetic tree space. Here, one is given a phylogenetic tree T and wants to find a more parsimonious tree in the neighborhood of T. We study the complexity of this problem when the neighborhood contains all trees within distance k for several classic distance functions. For the nearest neighbor interchange (NNI), subtree prune and regraft (SPR), tree bisection and reconnection (TBR), and edge contraction and refinement (ECR) distances, we show that, under the exponential time hypothesis, there are no algorithms with running time |I|^o(k) where |I| is the total input size. Hence, brute-force algorithms with running time |X|^𝒪(k) ⋅ |I| are essentially optimal. In contrast to the above distances, we observe that for the sECR-distance, where the contracted edges are constrained to form a subtree, a better solution within distance k can be found in k^𝒪(k) ⋅ |I|^𝒪(1) time. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18148"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18148">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Christian Komusiewicz, Simone Linz, Nils Morawietz, and Jannik Schestag. On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18148-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></a><br/><br/> <pre class="bibtex">@InProceedings{komusiewicz_et_al:LIPIcs.CPM.2023.18, author = {Komusiewicz, Christian and Linz, Simone and Morawietz, Nils and Schestag, Jannik}, title = {{On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {18:1--18: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.18}, URN = {urn:nbn:de:0030-drops-179729}, doi = {10.4230/LIPIcs.CPM.2023.18}, annote = {Keywords: phylogenetic trees, parameterized complexity, tree distances, NNI, TBR} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18148-input">@InProceedings{komusiewicz_et_al:LIPIcs.CPM.2023.18, author = {Komusiewicz, Christian and Linz, Simone and Morawietz, Nils and Schestag, Jannik}, title = {{On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {18:1--18: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.18}, URN = {urn:nbn:de:0030-drops-179729}, doi = {10.4230/LIPIcs.CPM.2023.18}, annote = {Keywords: phylogenetic trees, parameterized complexity, tree distances, NNI, TBR} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.19"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.19">DOI: 10.4230/LIPIcs.CPM.2023.19</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.19/LIPIcs.CPM.2023.19.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.19" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18149" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18149" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.19" data-bs-toggle="tooltip" data-title="String Factorization via Prefix Free Families" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Kraus, Matan"></span> <span data-key="dagstuhl.contributor.author" data-value="Lewenstein, Moshe"></span> <span data-key="dagstuhl.contributor.author" data-value="Popa, Alexandru"></span> <span data-key="dagstuhl.contributor.author" data-value="Porat, Ely"></span> <span data-key="dagstuhl.contributor.author" data-value="Sadia, Yonathan"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Approximation algorithms analysis"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.19"> String Factorization via Prefix Free Families </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Matan Kraus, Moshe Lewenstein, Alexandru Popa, Ely Porat, and Yonathan Sadia </p> <div class="row"> <div class="collapse" id="abstract-18149"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18149">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> A factorization of a string S is a partition of w into substrings u_1,… ,u_k such that S = u_1 u_2 ⋯ u_k. Such a partition is called equality-free if no two factors are equal: u_i ≠ u_j, ∀ i,j with i ≠ j. The maximum equality-free factorization problem is to find for a given string S, the largest integer k for which S admits an equality-free factorization with k factors. Equality-free factorizations have lately received attention because of their applications in DNA self-assembly. The best approximation algorithm known for the problem is the natural greedy algorithm, that chooses iteratively from left to right the shortest factor that does not appear before. This algorithm has a √n approximation ratio (SOFSEM 2020) and it is an open problem whether there is a better solution. Our main result is to show that the natural greedy algorithm is a Θ(n^{1/4}) approximation algorithm for the maximum equality-free factorization problem. Thus, we disprove one of the conjectures of Mincu and Popa (SOFSEM 2020) according to which the greedy algorithm is a Θ(√n) approximation. The most challenging part of the proof is to show that the greedy algorithm is an O(n^{1/4}) approximation. We obtain this algorithm via prefix free factor families, i.e. a set of non-overlapping factors of the string which are pairwise non-prefixes of each other. In the paper we show the relation between prefix free factor families and the maximum equality-free factorization. Moreover, as a byproduct we present another approximation algorithm that achieves an approximation ratio of O(n^{1/4}) that we believe is of independent interest and may lead to improved algorithms. We then show that the natural greedy algorithm has an approximation ratio that is Ω(n^{1/4}) via a clever analysis which shows that the greedy algorithm is Θ(n^{1/4}) for the maximum equality-free factorization problem. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18149"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18149">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Matan Kraus, Moshe Lewenstein, Alexandru Popa, Ely Porat, and Yonathan Sadia. String Factorization via Prefix Free Families. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 19:1-19:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18149-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></a><br/><br/> <pre class="bibtex">@InProceedings{kraus_et_al:LIPIcs.CPM.2023.19, author = {Kraus, Matan and Lewenstein, Moshe and Popa, Alexandru and Porat, Ely and Sadia, Yonathan}, title = {{String Factorization via Prefix Free Families}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {19:1--19:10}, 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.19}, URN = {urn:nbn:de:0030-drops-179738}, doi = {10.4230/LIPIcs.CPM.2023.19}, annote = {Keywords: string factorization, NP-hard problem, approximation algorithm} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18149-input">@InProceedings{kraus_et_al:LIPIcs.CPM.2023.19, author = {Kraus, Matan and Lewenstein, Moshe and Popa, Alexandru and Porat, Ely and Sadia, Yonathan}, title = {{String Factorization via Prefix Free Families}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {19:1--19:10}, 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.19}, URN = {urn:nbn:de:0030-drops-179738}, doi = {10.4230/LIPIcs.CPM.2023.19}, annote = {Keywords: string factorization, NP-hard problem, approximation algorithm} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.20"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.20">DOI: 10.4230/LIPIcs.CPM.2023.20</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.20/LIPIcs.CPM.2023.20.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.20" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18150" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18150" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.20" data-bs-toggle="tooltip" data-title="Improving the Sensitivity of MinHash Through Hash-Value Analysis" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Kucherov, Gregory"></span> <span data-key="dagstuhl.contributor.author" data-value="Skiena, Steven"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Bloom filters and hashing"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.20"> Improving the Sensitivity of MinHash Through Hash-Value Analysis </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Gregory Kucherov and Steven Skiena </p> <div class="row"> <div class="collapse" id="abstract-18150"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18150">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> MinHash sketching is an important algorithm for efficient document retrieval and bioinformatics. We show that the value of the matching MinHash codes convey additional information about the Jaccard similarity of S and T over and above the fact that the MinHash codes agree. This observation holds the potential to increase the sensitivity of minhash-based retrieval systems. We analyze the expected Jaccard similarity of two sets as a function of observing a matching MinHash value a under a reasonable prior distribution on intersection set sizes, and present a practical approach to using MinHash values to improve the sensitivity of traditional Jaccard similarity estimation, based on the Kolmogorov-Smirnov statistical test for sample distributions. Experiments over a wide range of hash function counts and set similarities show a small but consistent improvement over chance at predicting over/under-estimation, yielding an average accuracy of 61% over the range of experiments. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18150"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18150">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Gregory Kucherov and Steven Skiena. Improving the Sensitivity of MinHash Through Hash-Value Analysis. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18150-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></a><br/><br/> <pre class="bibtex">@InProceedings{kucherov_et_al:LIPIcs.CPM.2023.20, author = {Kucherov, Gregory and Skiena, Steven}, title = {{Improving the Sensitivity of MinHash Through Hash-Value Analysis}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {20:1--20:12}, 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.20}, URN = {urn:nbn:de:0030-drops-179740}, doi = {10.4230/LIPIcs.CPM.2023.20}, annote = {Keywords: MinHash sketching, sequence similarity, hashing} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18150-input">@InProceedings{kucherov_et_al:LIPIcs.CPM.2023.20, author = {Kucherov, Gregory and Skiena, Steven}, title = {{Improving the Sensitivity of MinHash Through Hash-Value Analysis}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {20:1--20:12}, 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.20}, URN = {urn:nbn:de:0030-drops-179740}, doi = {10.4230/LIPIcs.CPM.2023.20}, annote = {Keywords: MinHash sketching, sequence similarity, hashing} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.21"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.21">DOI: 10.4230/LIPIcs.CPM.2023.21</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.21/LIPIcs.CPM.2023.21.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.21" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18151" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18151" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.21" data-bs-toggle="tooltip" data-title="Suffix-Prefix Queries on a Dictionary" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Loukides, Grigorios"></span> <span data-key="dagstuhl.contributor.author" data-value="Pissis, Solon P."></span> <span data-key="dagstuhl.contributor.author" data-value="Thankachan, Sharma V."></span> <span data-key="dagstuhl.contributor.author" data-value="Zuba, Wiktor"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.21"> Suffix-Prefix Queries on a Dictionary </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Grigorios Loukides, Solon P. Pissis, Sharma V. Thankachan, and Wiktor Zuba </p> <div class="row"> <div class="collapse" id="abstract-18151"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18151">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> In the all-pairs suffix-prefix (APSP) problem, we are given a dictionary R of k strings, S_1,…,S_k, of total length n, and we are asked to find the length SPL_{i,j} of the longest string that is both a suffix of S_i and a prefix of S_j, for all i,j ∈ [1,k]. APSP is a classic problem in string algorithms with many applications in bioinformatics. When all strings of the dictionary are over an integer alphabet of size σ ≤ n^𝒪(1), APSP can be solved in the optimal 𝒪(n+k²) time with the use of the generalized suffix tree of the dictionary [Gusfield et al., Inf. Process. Lett. 1992]. In many bioinformatics applications, such as in sequence assembly, the size k of dictionary R is very large. In particular, k² usually dominates n, and thus the k² factor is the bottleneck both in the time and in the space complexity of such applications. We thus initiate a holistic study on several data structure variants of APSP. In particular, we consider the following types of queries: - One-to-One(i,j): output SPL_{i,j}. - One-to-All(i): output SPL_{i,j} for every j ∈ [1,k]. - Report(i,𝓁): output all distinct j ∈ [1,k] such that SPL_{i,j} ≥ 𝓁, where 𝓁 ≥ 0 is an integer. - Count(i,𝓁): output the number of distinct j ∈ [1,k] such that SPL_{i,j} ≥ 𝓁, where 𝓁 ≥ 0 is an integer. - Top(i,K): output K distinct j ∈ [1,k] with the highest values of SPL_{i,j} breaking ties arbitrarily. We assume the standard word RAM model of computation with word size w = Ω(log n) and an integer alphabet of size σ ≤ n^𝒪(1). We show the following upper bounds: Query | Space (words) | Query time | Note One-to-One(i,j) | 𝒪(n) | 𝒪(log log k) | Theorem 11 One-to-All(i) | 𝒪(n) | 𝒪(k) | Theorem 14 Report(i,𝓁) | 𝒪(n) | 𝒪(log n/log log n+output) | Theorem 19(i) Count(i,𝓁) | 𝒪(n) | 𝒪(log n/log log n) | Theorem 19(ii) Top(i,K) | 𝒪(n) | 𝒪(log² n/log log n+K) | Theorem 22 We also present efficient algorithms for constructing these data structures. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18151"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18151">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Grigorios Loukides, Solon P. Pissis, Sharma V. Thankachan, and Wiktor Zuba. Suffix-Prefix Queries on a Dictionary. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18151-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></a><br/><br/> <pre class="bibtex">@InProceedings{loukides_et_al:LIPIcs.CPM.2023.21, author = {Loukides, Grigorios and Pissis, Solon P. and Thankachan, Sharma V. and Zuba, Wiktor}, title = {{Suffix-Prefix Queries on a Dictionary}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {21:1--21:20}, 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.21}, URN = {urn:nbn:de:0030-drops-179757}, doi = {10.4230/LIPIcs.CPM.2023.21}, annote = {Keywords: all-pairs suffix-prefix, suffix-prefix queries, internal pattern matching} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18151-input">@InProceedings{loukides_et_al:LIPIcs.CPM.2023.21, author = {Loukides, Grigorios and Pissis, Solon P. and Thankachan, Sharma V. and Zuba, Wiktor}, title = {{Suffix-Prefix Queries on a Dictionary}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {21:1--21:20}, 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.21}, URN = {urn:nbn:de:0030-drops-179757}, doi = {10.4230/LIPIcs.CPM.2023.21}, annote = {Keywords: all-pairs suffix-prefix, suffix-prefix queries, internal pattern matching} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.22"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.22">DOI: 10.4230/LIPIcs.CPM.2023.22</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.22/LIPIcs.CPM.2023.22.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.22" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18152" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18152" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.22" data-bs-toggle="tooltip" data-title="Merging Sorted Lists of Similar Strings" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Myers, Gene"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Theory and algorithms for application domains"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.22"> Merging Sorted Lists of Similar Strings </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Gene Myers </p> <div class="row"> <div class="collapse" id="abstract-18152"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18152">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Merging T sorted, non-redundant lists containing M elements into a single sorted, non-redundant result of size N ≥ M/T is a classic problem typically solved practically in O(M log T) time with a priority-queue data structure the most basic of which is the simple heap. We revisit this problem in the situation where the list elements are strings and the lists contain many identical or nearly identical elements. By keeping simple auxiliary information with each heap node, we devise an O(M log T+S) worst-case method that performs no more character comparisons than the sum of the lengths of all the strings S, and another O(M log (T/e¯)+S) method that becomes progressively more efficient as a function of the fraction of equal elements e¯ = M/N between input lists, reaching linear time when the lists are all identical. The methods perform favorably in practice versus an alternate formulation based on a trie. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18152"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18152">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Gene Myers. Merging Sorted Lists of Similar Strings. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18152-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></a><br/><br/> <pre class="bibtex">@InProceedings{myers:LIPIcs.CPM.2023.22, author = {Myers, Gene}, title = {{Merging Sorted Lists of Similar Strings}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {22:1--22:15}, 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.22}, URN = {urn:nbn:de:0030-drops-179763}, doi = {10.4230/LIPIcs.CPM.2023.22}, annote = {Keywords: heap, trie, longest common prefix} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18152-input">@InProceedings{myers:LIPIcs.CPM.2023.22, author = {Myers, Gene}, title = {{Merging Sorted Lists of Similar Strings}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {22:1--22:15}, 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.22}, URN = {urn:nbn:de:0030-drops-179763}, doi = {10.4230/LIPIcs.CPM.2023.22}, annote = {Keywords: heap, trie, longest common prefix} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.23"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.23">DOI: 10.4230/LIPIcs.CPM.2023.23</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.23/LIPIcs.CPM.2023.23.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.23" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18153" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18153" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.23" data-bs-toggle="tooltip" data-title="PalFM-Index: FM-Index for Palindrome Pattern Matching" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Nagashita, Shinya"></span> <span data-key="dagstuhl.contributor.author" data-value="I, Tomohiro"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.23"> PalFM-Index: FM-Index for Palindrome Pattern Matching </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Shinya Nagashita and Tomohiro I </p> <div class="row"> <div class="collapse" id="abstract-18153"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18153">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> The palindrome pattern matching (pal-matching) is a kind of generalized pattern matching, in which two strings x and y of same length are considered to match (pal-match) if they have the same palindromic structures, i.e., for any possible 1 ≤ i < j ≤ |x| = |y|, x[i..j] is a palindrome if and only if y[i..j] is a palindrome. The pal-matching problem is the problem of searching for, in a text, the occurrences of the substrings that pal-match with a pattern. Given a text T of length n over an alphabet of size σ, an index for pal-matching is to support, given a pattern P of length m, the counting queries that compute the number occ of occurrences of P and the locating queries that compute the occurrences of P. The authors in [I et al., Theor. Comput. Sci., 2013] proposed an O(n lg n)-bit data structure to support the counting queries in O(m lg σ) time and the locating queries in O(m lg σ + occ) time. In this paper, we propose an FM-index type index for the pal-matching problem, which we call the PalFM-index, that occupies 2n lg min(σ, lg n) + 2n + o(n) bits of space and supports the counting queries in O(m) time. The PalFM-indexes can support the locating queries in O(m + Δ occ) time by adding n/Δ lg n + n + o(n) bits of space, where Δ is a parameter chosen from {1, 2, … , n} in the preprocessing phase. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18153"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18153">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Shinya Nagashita and Tomohiro I. PalFM-Index: FM-Index for Palindrome Pattern Matching. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18153-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></a><br/><br/> <pre class="bibtex">@InProceedings{nagashita_et_al:LIPIcs.CPM.2023.23, author = {Nagashita, Shinya and I, Tomohiro}, title = {{PalFM-Index: FM-Index for Palindrome Pattern Matching}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {23:1--23:15}, 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.23}, URN = {urn:nbn:de:0030-drops-179772}, doi = {10.4230/LIPIcs.CPM.2023.23}, annote = {Keywords: Palindrome matching, Generalized string pattern matching, Indexing} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18153-input">@InProceedings{nagashita_et_al:LIPIcs.CPM.2023.23, author = {Nagashita, Shinya and I, Tomohiro}, title = {{PalFM-Index: FM-Index for Palindrome Pattern Matching}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {23:1--23:15}, 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.23}, URN = {urn:nbn:de:0030-drops-179772}, doi = {10.4230/LIPIcs.CPM.2023.23}, annote = {Keywords: Palindrome matching, Generalized string pattern matching, Indexing} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.24"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.24">DOI: 10.4230/LIPIcs.CPM.2023.24</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.24/LIPIcs.CPM.2023.24.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.24" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18154" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18154" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.24" data-bs-toggle="tooltip" data-title="Computing MEMs on Repetitive Text Collections" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Navarro, Gonzalo"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data structures design and analysis"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.24"> Computing MEMs on Repetitive Text Collections </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Gonzalo Navarro </p> <div class="row"> <div class="collapse" id="abstract-18154"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18154">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> We consider the problem of computing the Maximal Exact Matches (MEMs) of a given pattern P[1..m] on a large repetitive text collection T[1..n], which is represented as a (hopefully much smaller) run-length context-free grammar of size g_{rl}. We show that the problem can be solved in time O(m² log^ε n), for any constant ε > 0, on a data structure of size O(g_{rl}). Further, on a locally consistent grammar of size O(δ log n/δ), the time decreases to O(m log m(log m + log^ε n)). The value δ is a function of the substring complexity of T and Ω(δ log n/δ) is a tight lower bound on the compressibility of repetitive texts T, so our structure has optimal size in terms of n and δ. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18154"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18154">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Gonzalo Navarro. Computing MEMs on Repetitive Text Collections. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18154-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></a><br/><br/> <pre class="bibtex">@InProceedings{navarro:LIPIcs.CPM.2023.24, author = {Navarro, Gonzalo}, title = {{Computing MEMs on Repetitive Text Collections}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {24:1--24:17}, 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.24}, URN = {urn:nbn:de:0030-drops-179787}, doi = {10.4230/LIPIcs.CPM.2023.24}, annote = {Keywords: grammar-based indices, maximal exact matches, locally consistent grammars, substring complexity} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18154-input">@InProceedings{navarro:LIPIcs.CPM.2023.24, author = {Navarro, Gonzalo}, title = {{Computing MEMs on Repetitive Text Collections}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {24:1--24:17}, 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.24}, URN = {urn:nbn:de:0030-drops-179787}, doi = {10.4230/LIPIcs.CPM.2023.24}, annote = {Keywords: grammar-based indices, maximal exact matches, locally consistent grammars, substring complexity} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.25"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.25">DOI: 10.4230/LIPIcs.CPM.2023.25</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.25/LIPIcs.CPM.2023.25.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.25" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18155" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18155" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.25" data-bs-toggle="tooltip" data-title="L-Systems for Measuring Repetitiveness" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Navarro, Gonzalo"></span> <span data-key="dagstuhl.contributor.author" data-value="Urbina, Cristian"></span> <span data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Combinatorics on words"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data compression"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.25"> L-Systems for Measuring Repetitiveness </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Gonzalo Navarro and Cristian Urbina </p> <div class="row"> <div class="collapse" id="abstract-18155"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18155">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> In order to use them for compression, we extend L-systems (without ε-rules) with two parameters d and n, and also a coding τ, which determines unambiguously a string w = τ(φ^d(s))[1:n], where φ is the morphism of the system, and s is its axiom. The length of the shortest description of an L-system generating w is known as 𝓁, and it is arguably a relevant measure of repetitiveness that builds on the self-similarities that arise in the sequence. In this paper, we deepen the study of the measure 𝓁 and its relation with a better-established measure called δ, which builds on substring complexity. Our results show that 𝓁 and δ are largely orthogonal, in the sense that one can be much larger than the other, depending on the case. This suggests that both mechanisms capture different kinds of regularities related to repetitiveness. We then show that the recently introduced NU-systems, which combine the capabilities of L-systems with bidirectional macro schemes, can be asymptotically strictly smaller than both mechanisms for the same fixed string family, which makes the size ν of the smallest NU-system the unique smallest reachable repetitiveness measure to date. We conclude that in order to achieve better compression, we should combine morphism substitution with copy-paste mechanisms. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18155"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18155">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Gonzalo Navarro and Cristian Urbina. L-Systems for Measuring Repetitiveness. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18155-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></a><br/><br/> <pre class="bibtex">@InProceedings{navarro_et_al:LIPIcs.CPM.2023.25, author = {Navarro, Gonzalo and Urbina, Cristian}, title = {{L-Systems for Measuring Repetitiveness}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {25:1--25:17}, 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.25}, URN = {urn:nbn:de:0030-drops-179792}, doi = {10.4230/LIPIcs.CPM.2023.25}, annote = {Keywords: L-systems, String morphisms, Repetitiveness measures, Text compression} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18155-input">@InProceedings{navarro_et_al:LIPIcs.CPM.2023.25, author = {Navarro, Gonzalo and Urbina, Cristian}, title = {{L-Systems for Measuring Repetitiveness}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {25:1--25:17}, 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.25}, URN = {urn:nbn:de:0030-drops-179792}, doi = {10.4230/LIPIcs.CPM.2023.25}, annote = {Keywords: L-systems, String morphisms, Repetitiveness measures, Text compression} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/LIPIcs.CPM.2023.26"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/LIPIcs.CPM.2023.26">DOI: 10.4230/LIPIcs.CPM.2023.26</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol259-cpm2023/LIPIcs.CPM.2023.26/LIPIcs.CPM.2023.26.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.26" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-18156" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-18156" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2023.26" data-bs-toggle="tooltip" data-title="MONI Can Find k-MEMs" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Tatarnikov, Igor"></span> <span data-key="dagstuhl.contributor.author" data-value="Shahrabi Farahani, Ardavan"></span> <span data-key="dagstuhl.contributor.author" data-value="Kashgouli, Sana"></span> <span data-key="dagstuhl.contributor.author" data-value="Gagie, Travis"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.26"> MONI Can Find k-MEMs </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Igor Tatarnikov, Ardavan Shahrabi Farahani, Sana Kashgouli, and Travis Gagie </p> <div class="row"> <div class="collapse" id="abstract-18156"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-18156">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Suppose we are asked to index a text T [0..n - 1] such that, given a pattern P [0..m - 1], we can quickly report the maximal substrings of P that each occur in T at least k times. We first show how we can add O (r log n) bits to Rossi et al.’s recent MONI index, where r is the number of runs in the Burrows-Wheeler Transform of T, such that it supports such queries in O (k m log n) time. We then show how, if we are given k at construction time, we can reduce the query time to O (m log n). </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-18156"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-18156">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Igor Tatarnikov, Ardavan Shahrabi Farahani, Sana Kashgouli, and Travis Gagie. MONI Can Find k-MEMs. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-18156-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></a><br/><br/> <pre class="bibtex">@InProceedings{tatarnikov_et_al:LIPIcs.CPM.2023.26, author = {Tatarnikov, Igor and Shahrabi Farahani, Ardavan and Kashgouli, Sana and Gagie, Travis}, title = {{MONI Can Find k-MEMs}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {26:1--26:14}, 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.26}, URN = {urn:nbn:de:0030-drops-179802}, doi = {10.4230/LIPIcs.CPM.2023.26}, annote = {Keywords: Compact data structures, Burrows-Wheeler Transform, run-length compression, maximal exact matches} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-18156-input">@InProceedings{tatarnikov_et_al:LIPIcs.CPM.2023.26, author = {Tatarnikov, Igor and Shahrabi Farahani, Ardavan and Kashgouli, Sana and Gagie, Travis}, title = {{MONI Can Find k-MEMs}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {26:1--26:14}, 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.26}, URN = {urn:nbn:de:0030-drops-179802}, doi = {10.4230/LIPIcs.CPM.2023.26}, annote = {Keywords: Compact data structures, Burrows-Wheeler Transform, run-length compression, maximal exact matches} }</textarea> </div> </div> </div> </div> </div> </div> <div class="col-sm-3 mt-2"> <h2>Filters</h2> <div class="free-text-filter mb-4"> <div class="input-group"> <input class="form-control no-outline" type="search" placeholder="Free Text Filter" aria-label="Free Text Filter" id="free-text-filter" maxlength="300"> </div> </div> <div class="grouped-metadata-filter" data-filter-key="dagstuhl.contributor.author"> <ul class="list-group"> <li class="list-group-item filter-headline list-group-item-dark"> <b><span class="count"></span> Authors</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item filter-item pinned -hidden" data-value="" data-key=""> <i class="bi bi-pin-angle-fill"></i> <span class="value"></span> <span class="action"><i><i class="bi bi-x-circle"></i></i></span> </li> <li class="list-group-item details buttons"> <span class="btn-group" role="group" aria-label="Show-All/Collapse"> <button type="button" class="btn btn-primary">Show All</button> <button type="button" class="btn btn-secondary">Collapse</button> </span> </li> <li class="list-group-item details show-all -hidden"> <button type="button" class="btn btn-primary">Show All</button> </li> <li class="list-group-item details filter-group-headline -expanded " data-group-selector="dagstuhl.contributor.author.A"> <b>A</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value " data-key="dagstuhl.contributor.author" data-value="Arroyuelo, Diego" data-group-selector="dagstuhl.contributor.author.A"> Arroyuelo, Diego <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value " data-key="dagstuhl.contributor.author" data-value="Asahiro, Yuichi" data-group-selector="dagstuhl.contributor.author.A"> Asahiro, Yuichi <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.B"> <b>B</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Bannai, Hideo" data-group-selector="dagstuhl.contributor.author.B"> Bannai, Hideo <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Bille, Philip" data-group-selector="dagstuhl.contributor.author.B"> Bille, Philip <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Boneh, Itai" data-group-selector="dagstuhl.contributor.author.B"> Boneh, Itai <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Bourhis, Pierre" data-group-selector="dagstuhl.contributor.author.B"> Bourhis, Pierre <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Boussidan, Aaron" data-group-selector="dagstuhl.contributor.author.B"> Boussidan, Aaron <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Bulteau, Laurent" data-group-selector="dagstuhl.contributor.author.B"> Bulteau, Laurent <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.C"> <b>C</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Cáceres, Manuel" data-group-selector="dagstuhl.contributor.author.C"> Cáceres, Manuel <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Castillo, Juan Pablo" data-group-selector="dagstuhl.contributor.author.C"> Castillo, Juan Pablo <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Charalampopoulos, Panagiotis" data-group-selector="dagstuhl.contributor.author.C"> Charalampopoulos, Panagiotis <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.D"> <b>D</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Dudek, Bartłomiej" data-group-selector="dagstuhl.contributor.author.D"> Dudek, Bartłomiej <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.E"> <b>E</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Equi, Massimo" data-group-selector="dagstuhl.contributor.author.E"> Equi, Massimo <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Eto, Hiroshi" data-group-selector="dagstuhl.contributor.author.E"> Eto, Hiroshi <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.F"> <b>F</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Fici, Gabriele" data-group-selector="dagstuhl.contributor.author.F"> Fici, Gabriele <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Fischer, Johannes" data-group-selector="dagstuhl.contributor.author.F"> Fischer, Johannes <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Fried, Dvir" data-group-selector="dagstuhl.contributor.author.F"> Fried, Dvir <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Funakoshi, Mitsuru" data-group-selector="dagstuhl.contributor.author.F"> Funakoshi, Mitsuru <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.G"> <b>G</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Gabory, Esteban" data-group-selector="dagstuhl.contributor.author.G"> Gabory, Esteban <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Gagie, Travis" data-group-selector="dagstuhl.contributor.author.G"> Gagie, Travis <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Gambette, Philippe" data-group-selector="dagstuhl.contributor.author.G"> Gambette, Philippe <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Gawrychowski, Paweł" data-group-selector="dagstuhl.contributor.author.G"> Gawrychowski, Paweł <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Ghazawi, Samah" data-group-selector="dagstuhl.contributor.author.G"> Ghazawi, Samah <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Gong, Mingyang" data-group-selector="dagstuhl.contributor.author.G"> Gong, Mingyang <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Gourdel, Garance" data-group-selector="dagstuhl.contributor.author.G"> Gourdel, Garance <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Gørtz, Inge Li" data-group-selector="dagstuhl.contributor.author.G"> Gørtz, Inge Li <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.H"> <b>H</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Hampson, Christopher" data-group-selector="dagstuhl.contributor.author.H"> Hampson, Christopher <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Harvey, Daniel J." data-group-selector="dagstuhl.contributor.author.H"> Harvey, Daniel J. <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.I"> <b>I</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="I, Tomohiro" data-group-selector="dagstuhl.contributor.author.I"> I, Tomohiro <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Iliopoulos, Costas S." data-group-selector="dagstuhl.contributor.author.I"> Iliopoulos, Costas S. <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.J"> <b>J</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Jansson, Jesper" data-group-selector="dagstuhl.contributor.author.J"> Jansson, Jesper <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.K"> <b>K</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Kashgouli, Sana" data-group-selector="dagstuhl.contributor.author.K"> Kashgouli, Sana <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Kim, Sung-Hwan" data-group-selector="dagstuhl.contributor.author.K"> Kim, Sung-Hwan <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Kociumaka, Tomasz" data-group-selector="dagstuhl.contributor.author.K"> Kociumaka, Tomasz <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Komusiewicz, Christian" data-group-selector="dagstuhl.contributor.author.K"> Komusiewicz, Christian <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Köppl, Dominik" data-group-selector="dagstuhl.contributor.author.K"> Köppl, Dominik <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Kraus, Matan" data-group-selector="dagstuhl.contributor.author.K"> Kraus, Matan <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Kucherov, Gregory" data-group-selector="dagstuhl.contributor.author.K"> Kucherov, Gregory <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Kurita, Kazuhiro" data-group-selector="dagstuhl.contributor.author.K"> Kurita, Kazuhiro <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.L"> <b>L</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Landau, Gad M." data-group-selector="dagstuhl.contributor.author.L"> Landau, Gad M. <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Lewenstein, Moshe" data-group-selector="dagstuhl.contributor.author.L"> Lewenstein, Moshe <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Lim, Zara" data-group-selector="dagstuhl.contributor.author.L"> Lim, Zara <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Lin, Guohui" data-group-selector="dagstuhl.contributor.author.L"> Lin, Guohui <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Linz, Simone" data-group-selector="dagstuhl.contributor.author.L"> Linz, Simone <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Lipták, Zsuzsanna" data-group-selector="dagstuhl.contributor.author.L"> Lipták, Zsuzsanna <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Loukides, Grigorios" data-group-selector="dagstuhl.contributor.author.L"> Loukides, Grigorios <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.M"> <b>M</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Mäkinen, Veli" data-group-selector="dagstuhl.contributor.author.M"> Mäkinen, Veli <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Meijer-van de Griend, Arianne" data-group-selector="dagstuhl.contributor.author.M"> Meijer-van de Griend, Arianne <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Miclăuş, Adrian" data-group-selector="dagstuhl.contributor.author.M"> Miclăuş, Adrian <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Miyano, Eiji" data-group-selector="dagstuhl.contributor.author.M"> Miyano, Eiji <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Morawietz, Nils" data-group-selector="dagstuhl.contributor.author.M"> Morawietz, Nils <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Mwaniki, Moses Njagi" data-group-selector="dagstuhl.contributor.author.M"> Mwaniki, Moses Njagi <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Myers, Gene" data-group-selector="dagstuhl.contributor.author.M"> Myers, Gene <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.N"> <b>N</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Nagashita, Shinya" data-group-selector="dagstuhl.contributor.author.N"> Nagashita, Shinya <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Nakashima, Yuto" data-group-selector="dagstuhl.contributor.author.N"> Nakashima, Yuto <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Navarro, Gonzalo" data-group-selector="dagstuhl.contributor.author.N"> Navarro, Gonzalo <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.O"> <b>O</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Olivares, Francisco" data-group-selector="dagstuhl.contributor.author.O"> Olivares, Francisco <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Ono, Hirotaka" data-group-selector="dagstuhl.contributor.author.O"> Ono, Hirotaka <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.P"> <b>P</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Pedersen, Max Rishøj" data-group-selector="dagstuhl.contributor.author.P"> Pedersen, Max Rishøj <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Pisanti, Nadia" data-group-selector="dagstuhl.contributor.author.P"> Pisanti, Nadia <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Pissis, Solon P." data-group-selector="dagstuhl.contributor.author.P"> Pissis, Solon P. <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Pokorski, Karol" data-group-selector="dagstuhl.contributor.author.P"> Pokorski, Karol <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Popa, Alexandru" data-group-selector="dagstuhl.contributor.author.P"> Popa, Alexandru <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Porat, Ely" data-group-selector="dagstuhl.contributor.author.P"> Porat, Ely <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Prezza, Nicola" data-group-selector="dagstuhl.contributor.author.P"> Prezza, Nicola <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.R"> <b>R</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Radoszewski, Jakub" data-group-selector="dagstuhl.contributor.author.R"> Radoszewski, Jakub <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Romana, Giuseppe" data-group-selector="dagstuhl.contributor.author.R"> Romana, Giuseppe <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Rytter, Wojciech" data-group-selector="dagstuhl.contributor.author.R"> Rytter, Wojciech <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.S"> <b>S</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Sadia, Yonathan" data-group-selector="dagstuhl.contributor.author.S"> Sadia, Yonathan <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Schestag, Jannik" data-group-selector="dagstuhl.contributor.author.S"> Schestag, Jannik <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Sciortino, Marinella" data-group-selector="dagstuhl.contributor.author.S"> Sciortino, Marinella <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Seto, Kazuhisa" data-group-selector="dagstuhl.contributor.author.S"> Seto, Kazuhisa <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Shahrabi Farahani, Ardavan" data-group-selector="dagstuhl.contributor.author.S"> Shahrabi Farahani, Ardavan <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Skiena, Steven" data-group-selector="dagstuhl.contributor.author.S"> Skiena, Steven <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Starikovskaya, Tatiana" data-group-selector="dagstuhl.contributor.author.S"> Starikovskaya, Tatiana <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Steiner, Teresa Anna" data-group-selector="dagstuhl.contributor.author.S"> Steiner, Teresa Anna <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Stordalen, Tord Joakim" data-group-selector="dagstuhl.contributor.author.S"> Stordalen, Tord Joakim <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Sung, Wing-Kin" data-group-selector="dagstuhl.contributor.author.S"> Sung, Wing-Kin <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Sweering, Michelle" data-group-selector="dagstuhl.contributor.author.S"> Sweering, Michelle <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.T"> <b>T</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Tanaka, Shunichi" data-group-selector="dagstuhl.contributor.author.T"> Tanaka, Shunichi <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Tatarnikov, Igor" data-group-selector="dagstuhl.contributor.author.T"> Tatarnikov, Igor <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Thankachan, Sharma V." data-group-selector="dagstuhl.contributor.author.T"> Thankachan, Sharma V. <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.U"> <b>U</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Uno, Takeaki" data-group-selector="dagstuhl.contributor.author.U"> Uno, Takeaki <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Urbina, Cristian" data-group-selector="dagstuhl.contributor.author.U"> Urbina, Cristian <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.W"> <b>W</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Waleń, Tomasz" data-group-selector="dagstuhl.contributor.author.W"> Waleń, Tomasz <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.Z"> <b>Z</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Zuba, Wiktor" data-group-selector="dagstuhl.contributor.author.Z"> Zuba, Wiktor <span class="action"><i class="bi bi-plus-circle"></i></span> </li> </ul> </div> <br /> <div class="grouped-metadata-filter" data-filter-key="dagstuhl.subject.classification"> <ul class="list-group"> <li class="list-group-item filter-headline list-group-item-dark"> <b><span class="count"></span> Subjects</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item filter-item pinned -hidden" data-value="" data-key=""> <i class="bi bi-pin-angle-fill"></i> <span class="value"></span> <span class="action"><i><i class="bi bi-x-circle"></i></i></span> </li> <li class="list-group-item details buttons"> <span class="btn-group" role="group" aria-label="Show-All/Collapse"> <button type="button" class="btn btn-primary">Show All</button> <button type="button" class="btn btn-secondary">Collapse</button> </span> </li> <li class="list-group-item details show-all -hidden"> <button type="button" class="btn btn-primary">Show All</button> </li> <li class="list-group-item details filter-group-headline -expanded " data-group-selector="dagstuhl.subject.classification.Applied computing"> <b>Applied computing</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value " data-key="dagstuhl.subject.classification" data-value="Applied computing → Computational biology" data-group-selector="dagstuhl.subject.classification.Applied computing"> Applied computing → Computational biology <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value " data-key="dagstuhl.subject.classification" data-value="Applied computing → Computational genomics" data-group-selector="dagstuhl.subject.classification.Applied computing"> Applied computing → Computational genomics <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value " data-key="dagstuhl.subject.classification" data-value="Applied computing → Molecular evolution" data-group-selector="dagstuhl.subject.classification.Applied computing"> Applied computing → Molecular evolution <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.subject.classification.Computing methodologies"> <b>Computing methodologies</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Computing methodologies → Artificial intelligence" data-group-selector="dagstuhl.subject.classification.Computing methodologies"> Computing methodologies → Artificial intelligence <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.subject.classification.Hardware"> <b>Hardware</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Hardware → Theorem proving and SAT solving" data-group-selector="dagstuhl.subject.classification.Hardware"> Hardware → Theorem proving and SAT solving <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.subject.classification.Information systems"> <b>Information systems</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems → Information retrieval query processing" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems → Information retrieval query processing <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.subject.classification.Mathematics of computing"> <b>Mathematics of computing</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Combinatoric problems" data-group-selector="dagstuhl.subject.classification.Mathematics of computing"> Mathematics of computing → Combinatoric problems <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Combinatorics on words" data-group-selector="dagstuhl.subject.classification.Mathematics of computing"> Mathematics of computing → Combinatorics on words <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Discrete mathematics" data-group-selector="dagstuhl.subject.classification.Mathematics of computing"> Mathematics of computing → Discrete mathematics <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Mathematics of computing → Graph algorithms" data-group-selector="dagstuhl.subject.classification.Mathematics of computing"> Mathematics of computing → Graph algorithms <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.subject.classification.Theory of computation"> <b>Theory of computation</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Approximation algorithms analysis" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Approximation algorithms analysis <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Bloom filters and hashing" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Bloom filters and hashing <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data compression" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Data compression <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data structures and algorithms for data management" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Data structures and algorithms for data management <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data structures design and analysis" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Data structures design and analysis <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Design and analysis of algorithms" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Design and analysis of algorithms <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Discrete optimization" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Discrete optimization <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Formal languages and automata theory" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Formal languages and automata theory <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Graph algorithms analysis" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Graph algorithms analysis <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Parallel algorithms" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Parallel algorithms <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Parameterized complexity and exact algorithms" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Parameterized complexity and exact algorithms <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Pattern matching" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Pattern matching <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Quantum computation theory" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Quantum computation theory <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Theory and algorithms for application domains" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Theory and algorithms for application domains <span class="action"><i class="bi bi-plus-circle"></i></span> </li> </ul> </div> </div> </div> <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="34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)"> <div style="margin-top: 20vh" class="centered-loader"><div class="loader"></div></div> <iframe class="-hidden"></iframe> </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> </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/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-2024-10-22"></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/volume/LIPIcs-volume-259/-/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 view = { trackInvestigation: function(e) { const $entity = $(e.currentTarget).parent().parent(); const permanentId = $entity.attr('data-permanent-id'); $.ajax({ url: '/entities/' + permanentId + '/_investigation', type: 'get', }); }, initialize: function() { $('a.investigation').on('click', view.trackInvestigation); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const view = { $el: { root: $('.grouped-metadata-filter'), freeTextFilter: $('#free-text-filter') }, appliedFilters: { freeText: [] }, methods: { toggleDetails: function(e) { var $current = $(e.currentTarget); var $parent = $current.parent(); $parent.toggleClass('-expanded'); }, toggleGroup: function(e) { var $current = $(e.currentTarget); var selector = $current.attr('data-group-selector'); $current.toggleClass('-expanded'); $('.filter-item[data-group-selector="' + selector + '"]').toggleClass('-hidden'); }, toggleFilter: function(e) { var $current = $(e.currentTarget); var key = $current.attr('data-key'); var value = $current.attr('data-value'); if (view.appliedFilters[key] === undefined) { view.appliedFilters[key] = []; } var index = view.appliedFilters[key].indexOf(value); if (index !== -1) { view.appliedFilters[key].splice(index, 1); $('.grouped-metadata-filter[data-filter-key="'+key+'"]').find('.pinned[data-value="'+value+'"]').remove(); } else { view.appliedFilters[key].push(value); var $template = $('.grouped-metadata-filter[data-filter-key="'+key+'"]').find('.pinned.-hidden'); var $filter = $template.clone(); $filter.find('.value').html(value); $filter.attr('data-value', value) .attr('data-key', key) .removeClass('-hidden') .insertAfter($template) .on('click', view.methods.toggleFilter); } var event = (index !== -1) ? 'removeFilter' : 'addFilter'; var filterCount = 0; for(var filterKey in view.appliedFilters) { filterCount += view.appliedFilters[filterKey].length; } $(document).trigger('grouped-metadata-filter:' + event, { key: key, value: value, appliedFilters: view.appliedFilters, filterCount: filterCount }); }, setFreeTextFilter: function(e) { var $current = $(e.currentTarget); var value = $current.val().trim(); if (value === '') { view.appliedFilters.freeText = [] } else { view.appliedFilters.freeText = [ value ]; } var filterCount = 0; for(var filterKey in view.appliedFilters) { filterCount += view.appliedFilters[filterKey].length; } $(document).trigger('grouped-metadata-filter:addFilter', { key: 'free-text', value: value, appliedFilters: view.appliedFilters, filterCount: filterCount }); }, dropAllFilters: function() { $('.grouped-metadata-filter').find('.filter-item.pinned:not(.-hidden)').click(); $('#free-text-filter').val('').trigger('keyup'); }, expandAllGroups: function(e) { var $current = $(e.currentTarget); $current.parent().parent().parent().find('.filter-group-headline:not(.-expanded)').click(); }, collapseAllGroups: function(e) { var $current = $(e.currentTarget); var $filter = $current.parent().parent().parent(); $filter.find('.filter-group-headline.-expanded').click(); $filter.find('.filter-headline').click(); $filter.find('.filter-headline').click(); } }, initialize: function() { view.$el.root.each(function() { var count = $(this).find('.filter-item.value').length; $(this).find('.filter-headline .count').text(count); }); view.$el.root.find('.filter-group-headline').on('click', view.methods.toggleGroup); view.$el.root.find('.filter-item').on('click', view.methods.toggleFilter); view.$el.root.find('.filter-headline').on('click', view.methods.toggleDetails); view.$el.root.find('.buttons .btn-primary').on('click', view.methods.expandAllGroups); view.$el.root.find('.buttons .btn-secondary').on('click', view.methods.collapseAllGroups); view.$el.freeTextFilter.on('keyup', view.methods.setFreeTextFilter); view.$el.freeTextFilter.on('search', view.methods.setFreeTextFilter); $(document).on('grouped-metadata-filter:dropAllFilters', view.methods.dropAllFilters); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const view = { normalize: function(string) { return string.normalize('NFD').replace(/[\u0300-\u036f]/g, ""); }, applyFilters: function(e, data) { var $documents = $('.document'); var $noResults = $('.no-results'); $documents.each(function() { var $document = $(this); var matches = 0; for(var filterKey in data.appliedFilters) { var values = data.appliedFilters[filterKey]; if (filterKey === 'freeText' && values[0] !== undefined && values[0] !== '') { var regex = new RegExp(view.normalize(values[0].toLowerCase()), 'i'); matches += view.normalize($document.html()).match(regex) ? 1 : 0; } else { values.forEach(function (value) { matches += $document.find('.selectors').find('[data-key="' + filterKey + '"][data-value="' + value + '"]').length }); } } if (matches === data.filterCount) { $document.removeClass('-hidden'); } else { $document.addClass('-hidden') } }); if ($documents.parent().find('.document:not(.-hidden').length === 0) { $noResults.removeClass('-hidden'); } else { $noResults.addClass('-hidden'); } document.getElementById('end-of-header').scrollIntoView(); var filterInfo = ''; if (data.filterCount === 1) { filterInfo = '1 filter applied   ×'; } else if (data.filterCount > 1) { filterInfo = data.filterCount + ' filters applied   ×'; } $('._filter-info').html(filterInfo); if (data.appliedFilters.freeText[0] !== undefined && data.appliedFilters.freeText[0] !== '') { $('#free-text-filter').addClass('-active'); } else { $('#free-text-filter').removeClass('-active'); } }, initialize: function() { $(document).on('grouped-metadata-filter:addFilter', view.applyFilters); $(document).on('grouped-metadata-filter:removeFilter', view.applyFilters); } }; view.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() { $('._filter-info').on('click', function() { $(document).trigger('grouped-metadata-filter:dropAllFilters'); }); }); </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"> $(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() { const innerAnchors = [ 'resource-articles', 'cfp-si-resources', 'cfp-si-autonomous-systems-and-knowledge-graphs' ]; let 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); } } $('[data-tab-link]').on('click', function(e) { const $target = $(e.currentTarget); let href = $target.attr('href'); let scrollLink = null; if (href === '#cfp-si-list') { scrollLink = href; href = '#cfp'; } try { console.log(href); $(href+'-tab').tab('show'); } catch(e) { } console.log(scrollLink); if (scrollLink !== null) { setTimeout(function() { $(scrollLink)[0].scrollIntoView(); }, 200); } else { setTimeout(function() { window.scrollTo(0,0); }, 200); } }); } }, 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

34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)