Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

New Trends in Text Algorithms

2018/31/D/ST6/03991

Keywords:

text algorithms pattern matching machine learning

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST6_7: Artificial intelligence, intelligent systems, multi-agent systems

Panel:

ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution :

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr hab. Jakub Radoszewski 

Number of co-investigators in the project: 5

Call: SONATA 14 - announced on 2018-09-14

Amount awarded: 565 740 PLN

Project start date (Y-m-d): 2019-07-09

Project end date (Y-m-d): 2023-03-08

Project duration:: 44 months (the same as in the proposal)

Project status: Project settled

Project description

Download the project description in a pdf file

Note - project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.

Equipment purchased [PL]

  1. Laptop 2 szt. (4 907 PLN)

Information in the final report

  • Publication in academic press/journals (8)
  • Articles in post-conference publications (22)
  1. Efficient Computation of Sequence Mappability
    Authors:
    Panagiotis Charalampopoulos, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Juliusz Straszyński
    Academic press:
    Algorithmica (rok: 2022, tom: 84 (5), strony: 1418-1440), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-022-00934-y - link to the publication
  2. A note on the maximum number of k-powers in a finite word
    Authors:
    Shuo Li, Jakub Pachocki, Jakub Radoszewski
    Academic press:
    Electronic Journal of Combinatorics , Wydawca: nie dotyczy
    Status:
    Submitted
    DOI:
    brak - link to the publication
  3. Circular pattern matching with k mismatches
    Authors:
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
    Academic press:
    Journal of Computer and System Sciences (rok: 2021, tom: 115, strony: 73-85), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2020.07.003 - link to the publication
  4. Shortest covers of all cyclic shifts of a string
    Authors:
    Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
    Academic press:
    Theoretical Computer Science (rok: 2021, tom: 866, strony: 70-81), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2021.03.011 - link to the publication
  5. Internal Dictionary Matching
    Authors:
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń
    Academic press:
    Algorithmica (rok: 2021, tom: 83 (7), strony: 2142-2169), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-021-00821-y - link to the publication
  6. Pattern Masking for Dictionary Matching: Theory and Practice
    Authors:
    Panagiotis Charalampopoulos, Huiping Chen, Peter Christen, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski
    Academic press:
    Algorithmica , Wydawca: Springer
    Status:
    Submitted
    DOI:
    brak - link to the publication
  7. Optimal skeleton and reduced Huffman trees
    Authors:
    Shmuel T. Klein, Jakub Radoszewski, Tamar C. Serebro, Dana Shapira
    Academic press:
    Theoretical Computer Science (rok: 2021, tom: 852, strony: 157-171), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2020.11.025 - link to the publication
  8. k-Approximate Quasiperiodicity Under Hamming and Edit Distance
    Authors:
    Aleksander Kędzierski, Jakub Radoszewski
    Academic press:
    Algorithmica (rok: 2022, tom: 84 (3), strony: 566-589), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-021-00842-7 - link to the publication
  1. Approximating Longest Common Substring with k mismatches: Theory and Practice
    Authors:
    Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Tatiana Starikovskaya
    Conference:
    31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2020-06-17 - 2020-06-19
    Status:
    Published
  2. Internal Dictionary Matching
    Authors:
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń
    Conference:
    30th International Symposium on Algorithms and Computation, ISAAC 2019 (rok: 2019, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2019-12-08 - 2019-12-11
    Status:
    Published
  3. Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String
    Authors:
    Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba
    Conference:
    34th Annual Symposium on Combinatorial Pattern Matching, CPM 2023 (rok: 2023, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2023-06-26 - 2023-06-28
    Status:
    Published
  4. Rectangular Tile Covers of 2D-Strings
    Authors:
    Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
    Conference:
    33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, (rok: 2022, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2022.06.27 - 2022.06.29
    Status:
    Published
  5. The Number of Repetitions in 2D-Strings
    Authors:
    Panagiotis Charalampopoulos, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba
    Conference:
    28th Annual European Symposium on Algorithms, ESA 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2020-09-07 - 2020-09-09
    Status:
    Published
  6. Computing Covers of 2D-Strings
    Authors:
    Panagiotis Charalampopoulos, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba
    Conference:
    32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021 (rok: 2021, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2021.07.05 - 2021.07.07
    Status:
    Published
  7. Faster Algorithms for Longest Common Substring
    Authors:
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski
    Conference:
    29th Annual European Symposium on Algorithms, ESA 2021 (rok: 2021, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2021-09-06 - 2021-09-08
    Status:
    Published
  8. Hardness of Detecting Abelian and Additive Square Factors in Strings
    Authors:
    Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
    Conference:
    29th Annual European Symposium on Algorithms, ESA 2021 (rok: 2021, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2021-09-06 - 2021-09-08
    Status:
    Published
  9. Pattern Masking for Dictionary Matching
    Authors:
    Panagiotis Charalampopoulos, Huiping Chen, Peter Christen, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski
    Conference:
    32nd International Symposium on Algorithms and Computation, ISAAC 2021 (rok: 2021, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2021-12-06 - 2021-12-08
    Status:
    Published
  10. Shortest Covers of All Cyclic Shifts of a String
    Authors:
    Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
    Conference:
    Algorithms and Computation - 14th International Conference, WALCOM 2020 (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 2020-03-31 - 2020-04-02
    Status:
    Published
  11. String Covers of a Tree
    Authors:
    Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
    Conference:
    28th International Symposium on String Processing and Information Retrieval, SPIRE 2021 (rok: 2021, ), Wydawca: Springer
    Data:
    konferencja 2021-10-04 - 2021-10-06
    Status:
    Published
  12. Counting Distinct Patterns in Internal Dictionary Matching
    Authors:
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
    Conference:
    31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2020-06-17 - 2020-06-19
    Status:
    Published
  13. Efficient Enumeration of Distinct Factors Using Package Representations
    Authors:
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba
    Conference:
    String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020 (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 2020-10-13 - 2020-10-15
    Status:
    Published
  14. Longest Palindromic Substring in Sublinear Time
    Authors:
    Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski
    Conference:
    33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022 (rok: 2022, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2022.06.27 - 2022.06.29
    Status:
    Published
  15. k-Approximate Quasiperiodicity under Hamming and Edit Distance
    Authors:
    Aleksander Kędzierski, Jakub Radoszewski
    Conference:
    31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2020-06-17 - 2020-06-19
    Status:
    Published
  16. Approximate Circular Pattern Matching
    Authors:
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba
    Conference:
    30th Annual European Symposium on Algorithms, ESA 2022 (rok: 2022, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2022-09-05 - 2022-09-09
    Status:
    Published
  17. Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications
    Authors:
    Esteban Gabory, Moses Njagi Mwaniki, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski, Michelle Sweering, Wiktor Zuba
    Conference:
    34th Annual Symposium on Combinatorial Pattern Matching, CPM 2023 (rok: 2023, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2023-06-26 - 2023-06-28
    Status:
    Published
  18. Internal Quasiperiod Queries
    Authors:
    Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
    Conference:
    String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020 (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 2020-10-13 - 2020-10-15
    Status:
    Published
  19. Efficient Computation of 2-Covers of a String
    Authors:
    Jakub Radoszewski, Juliusz Straszyński
    Conference:
    28th Annual European Symposium on Algorithms, ESA 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2020-09-07 - 2020-09-09
    Status:
    Published
  20. Linear-Time Computation of Shortest Covers of All Rotations of a String
    Authors:
    Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba
    Conference:
    33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022 (rok: 2022, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik}
    Data:
    konferencja 2022.06.27 - 2022.06.29
    Status:
    Published
  21. Subsequence Covers of Words
    Authors:
    Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba
    Conference:
    29th International Symposium on String Processing and Information Retrieval, SPIRE 2022 (rok: 2022, ), Wydawca: Springer
    Data:
    konferencja 2022-11-08 - 2022-11-10
    Status:
    Published
  22. Unary Words Have the Smallest Levenshtein k-Neighbourhoods
    Authors:
    Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Tomasz Waleń, Wiktor Zuba
    Conference:
    31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 2020-06-17 - 2020-06-19
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy