LIPIcs, Volume 191
CPM 2021, July 5-7, 2021, Wrocław, Poland
Editors: Paweł Gawrychowski and Tatiana Starikovskaya
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Gabriel Bathie, Tomasz Kociumaka, and Tatiana Starikovskaya. Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 10:1-10:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bathie_et_al:LIPIcs.ISAAC.2023.10, author = {Bathie, Gabriel and Kociumaka, Tomasz and Starikovskaya, Tatiana}, title = {{Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {10:1--10:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.10}, URN = {urn:nbn:de:0030-drops-193124}, doi = {10.4230/LIPIcs.ISAAC.2023.10}, annote = {Keywords: Approximate pattern matching, streaming algorithms, palindromes, squares} }
Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
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)
@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} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Tatiana Starikovskaya. Streaming Pattern Matching (Invited Talk). In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{starikovskaya:LIPIcs.ISAAC.2021.1, author = {Starikovskaya, Tatiana}, title = {{Streaming Pattern Matching}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.1}, URN = {urn:nbn:de:0030-drops-154345}, doi = {10.4230/LIPIcs.ISAAC.2021.1}, annote = {Keywords: Streaming algorithms, Pattern matching, Hamming distance, Edit distance} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Gabriel Bathie and Tatiana Starikovskaya. Property Testing of Regular Languages with Applications to Streaming Property Testing of Visibly Pushdown Languages. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 119:1-119:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bathie_et_al:LIPIcs.ICALP.2021.119, author = {Bathie, Gabriel and Starikovskaya, Tatiana}, title = {{Property Testing of Regular Languages with Applications to Streaming Property Testing of Visibly Pushdown Languages}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {119:1--119:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.119}, URN = {urn:nbn:de:0030-drops-141881}, doi = {10.4230/LIPIcs.ICALP.2021.119}, annote = {Keywords: property testing, regular languages, streaming algorithms, visibly pushdown languages} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Paweł Gawrychowski and Tatiana Starikovskaya. LIPIcs, Volume 191, CPM 2021, Complete Volume. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 1-404, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@Proceedings{gawrychowski_et_al:LIPIcs.CPM.2021, title = {{LIPIcs, Volume 191, CPM 2021, Complete Volume}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {1--404}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021}, URN = {urn:nbn:de:0030-drops-139509}, doi = {10.4230/LIPIcs.CPM.2021}, annote = {Keywords: LIPIcs, Volume 191, CPM 2021, Complete Volume} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Paweł Gawrychowski and Tatiana Starikovskaya. Front Matter, Table of Contents, Preface, Conference Organization. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 0:i-0:xiv, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{gawrychowski_et_al:LIPIcs.CPM.2021.0, author = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {0:i--0:xiv}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.0}, URN = {urn:nbn:de:0030-drops-139512}, doi = {10.4230/LIPIcs.CPM.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Hideo Bannai. Repetitions in Strings: A "Constant" Problem (Invited Talk). In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bannai:LIPIcs.CPM.2021.1, author = {Bannai, Hideo}, title = {{Repetitions in Strings: A "Constant" Problem}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.1}, URN = {urn:nbn:de:0030-drops-139523}, doi = {10.4230/LIPIcs.CPM.2021.1}, annote = {Keywords: Maximal repetitions, Squares, Lyndon words} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Michal Koucký. Computing Edit Distance (Invited Talk). In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{koucky:LIPIcs.CPM.2021.2, author = {Kouck\'{y}, Michal}, title = {{Computing Edit Distance}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.2}, URN = {urn:nbn:de:0030-drops-139534}, doi = {10.4230/LIPIcs.CPM.2021.2}, annote = {Keywords: edit distance, streaming algorithms, approximation algorithms, sketching} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Nadia Pisanti. On-Line Pattern Matching on D-Texts (Invited Talk). In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 3:1-3:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{pisanti:LIPIcs.CPM.2021.3, author = {Pisanti, Nadia}, title = {{On-Line Pattern Matching on D-Texts}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {3:1--3:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.3}, URN = {urn:nbn:de:0030-drops-139548}, doi = {10.4230/LIPIcs.CPM.2021.3}, annote = {Keywords: pattern matching, elastic-degenerate string, matrix multiplication} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Duncan Adamson, Vladimir V. Gusev, Igor Potapov, and Argyrios Deligkas. Ranking Bracelets in Polynomial Time. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 4:1-4:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{adamson_et_al:LIPIcs.CPM.2021.4, author = {Adamson, Duncan and Gusev, Vladimir V. and Potapov, Igor and Deligkas, Argyrios}, title = {{Ranking Bracelets in Polynomial Time}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {4:1--4:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.4}, URN = {urn:nbn:de:0030-drops-139554}, doi = {10.4230/LIPIcs.CPM.2021.4}, annote = {Keywords: Bracelets, Ranking, Necklaces} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Amihood Amir, Itai Boneh, and Eitan Kondratovsky. The k-Mappability Problem Revisited. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 5:1-5:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{amir_et_al:LIPIcs.CPM.2021.5, author = {Amir, Amihood and Boneh, Itai and Kondratovsky, Eitan}, title = {{The k-Mappability Problem Revisited}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.5}, URN = {urn:nbn:de:0030-drops-139566}, doi = {10.4230/LIPIcs.CPM.2021.5}, annote = {Keywords: Pattern Matching, Hamming Distance, Suffix Tree, Suffix Array} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Golnaz Badkobeh, Panagiotis Charalampopoulos, and Solon P. Pissis. Internal Shortest Absent Word Queries. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 6:1-6:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{badkobeh_et_al:LIPIcs.CPM.2021.6, author = {Badkobeh, Golnaz and Charalampopoulos, Panagiotis and Pissis, Solon P.}, title = {{Internal Shortest Absent Word Queries}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {6:1--6:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.6}, URN = {urn:nbn:de:0030-drops-139570}, doi = {10.4230/LIPIcs.CPM.2021.6}, annote = {Keywords: string algorithms, internal queries, shortest absent word, bit parallelism} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piątkowski. Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 7:1-7:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bannai_et_al:LIPIcs.CPM.2021.7, author = {Bannai, Hideo and K\"{a}rkk\"{a}inen, Juha and K\"{o}ppl, Dominik and Pi\k{a}tkowski, Marcin}, title = {{Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.7}, URN = {urn:nbn:de:0030-drops-139588}, doi = {10.4230/LIPIcs.CPM.2021.7}, annote = {Keywords: Burrows-Wheeler Transform, Lyndon words, Circular Suffix Array, Suffix Array Construction Algorithm} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Djamal Belazzougui, Dmitry Kosolobov, Simon J. Puglisi, and Rajeev Raman. Weighted Ancestors in Suffix Trees Revisited. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 8:1-8:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{belazzougui_et_al:LIPIcs.CPM.2021.8, author = {Belazzougui, Djamal and Kosolobov, Dmitry and Puglisi, Simon J. and Raman, Rajeev}, title = {{Weighted Ancestors in Suffix Trees Revisited}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {8:1--8:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.8}, URN = {urn:nbn:de:0030-drops-139594}, doi = {10.4230/LIPIcs.CPM.2021.8}, annote = {Keywords: suffix tree, weighted ancestors, irreducible LCP, deterministic substring hashing} }
Feedback for Dagstuhl Publishing