Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Aspects of grammar compression

2017/26/E/ST6/00191

Keywords:

Grammar compression SLP Recomrpession Word equations

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms

Panel:

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

Host institution :

Uniwersytet Wrocławski, Wydział Matematyki i Informatyki

woj. dolnośląskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr hab. Artur Jeż 

Number of co-investigators in the project: 8

Call: SONATA BIS 7 - announced on 2017-06-14

Amount awarded: 1 760 200 PLN

Project start date (Y-m-d): 2018-04-20

Project end date (Y-m-d): 2023-10-19

Project duration:: 66 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.

Information in the final report

  • Publication in academic press/journals (2)
  • Articles in post-conference publications (9)
  1. Balancing Straight-line Programs
    Authors:
    Moses Ganardi, Artur Jeż, Markus Lohrey
    Academic press:
    Journal of the ACM (rok: 2021, tom: 2,83611111111111, strony: 27:1–27:40), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3457389 - link to the publication
  2. The Smallest Grammar Problem Revisited
    Authors:
    Hideo Bannai, Momoko Hirayama, Danny Hucke, Shunsuke Inenaga, Artur Jeż, Markus Lohrey, Carl Philipp Reh
    Academic press:
    IEEE Transactions on Information Theory (rok: 2021, tom: 2,79236111111111, strony: 317–328), Wydawca: IEEE
    Status:
    Published
    DOI:
    10.1109/TIT.2020.3038147 - link to the publication
  1. Solving Word Equations (And Other Unification Problems) by Recompression
    Authors:
    Artur Jeż
    Conference:
    28th EACSL Annual Conference on Computer Science Logic (CSL 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 13–16.01.2020
    Status:
    Published
    DOI:
    link to the publication
  2. Parikh's Theorem Made Symbolic
    Authors:
    Matthew Hague, Artur Jeż, Anthony W. Lin
    Conference:
    51st ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2024) (rok: 2024, ), Wydawca: ACM
    Data:
    konferencja 17–19.01.2024
    Status:
    Published
  3. Data Path Queries over Embedded Graph Databases
    Authors:
    Diego Figueira, Artur Jeż, Anthony W. Lin
    Conference:
    International Conference on Management of Data (PODS '22); dawniej Principles of Database Systems (rok: 2022, ), Wydawca: ACM
    Data:
    konferencja 12–17.06.2022
    Status:
    Published
  4. Solving One Variable Word Equations in the Free Group in Cubic Time
    Authors:
    Robert Ferens, Artur Jeż
    Conference:
    38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (rok: 2021, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 16–18.03.2021
    Status:
    Published
    DOI:
    link to the publication
  5. Towards Better Compressed Representations
    Authors:
    Michał Gańczorz
    Conference:
    2020 Data Compression Conference (DCC 2020) (rok: 2020, ), Wydawca: IEEE Computer Society Conference Publishing Services
    Data:
    konferencja 24–27.03.2020
    Status:
    Published
  6. Using Statistical Encoding to Achieve Tree Succinctness Never Seen Before
    Authors:
    Michał Gańczorz
    Conference:
    37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
    Data:
    konferencja 10–13.03.2020
    Status:
    Published
    DOI:
    link to the publication
  7. Balancing Straight-Line Programs
    Authors:
    Moses Ganardi, Artur Jeż, Markus Lohrey
    Conference:
    IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (rok: 2019, ), Wydawca: IEEE
    Data:
    konferencja 9-12.11.2019
    Status:
    Published
  8. Decision Procedures for Sequence Theories
    Authors:
    Artur Jeż, Anthony W. Lin, Oliver Markgraf, Philipp Rümmer
    Conference:
    35th International Conference on Computer Aided Verification (CAV) (rok: 2023, ), Wydawca: Springer
    Data:
    konferencja 17–22.07.2023
    Status:
    Published
    DOI:
    link to the publication
  9. Entropy Lower Bounds for Dictionary Compression
    Authors:
    Michał Gańczorz
    Conference:
    30th Annual Symposium on Combinatorial Pattern Matching (CPM) (rok: 2019, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 2019-06-18–2019-06-20
    Status:
    Published
    DOI:
    link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy