Polish National Science Centre (NCN) grant 2017/26/E/ST6/00191
Aspects of grammar compression

Project closed: 04.2018–10.2023

Project focus

In this project, we want to investigate various aspects of grammar compression, both for words and for trees. This includes, but is not limited to, investigation of approximation ratios for various grammar compressors, running time lower bounds, comparisons with entropy compression, new models for tree compression as well as application of grammar compression in some areas in which it already has been shown to be successful.

For more information, see abstract of the project or its full description or contact project principal investigator, Artur Jeż.

Investigators

• Artur Jeż (principal investigator)
• Robert Ferens (investigator—PhD student; 2018–2023)
• Michał Gańczorz (investigator—PhD student; 2018–2020)
• Ihor Rystsov (2022)

Publications

• A. Jeż, A. W. Lin, M. Hague Parikh's Theorem Made Symbolic POPL 2024 [conference version, arXiv]
• A. Jeż, A. W. Lin, O. Markgraf, Ph. Rümmer Decision Procedures for Sequence Theories CAV 2023 [conference version, arXiv]
• D. Figueira, A. Jeż, A. W. Lin Data Path Queries over Embedded Graph Databases PODS 2022 [conference version]
• R. Ferens, A. Jeż Solving one variable word equations in the free group in cubic time STACS 2021 [arXiv]
• H. Bannai, M. Hirayama, D. Hucke, S. Inenaga, A. Jeż, M. Lohrey, C. Reh The Smallest Grammar Problem Revisited IEEE Transactions on Information Theory [arXiv, journal]
• M. Gańczorz Towards Better Compressed Representations DCC 2020 (poster) [arXiv]
• M. Gańczorz Using Statistical Encoding to Achieve Tree Succinctness Never Seen Before STACS 2020 [conference version, arXiv]
• M. Ganardi, A. Jeż, M. Lohrey Balancing Straight-Line Programs FOCS 2019; full version: JACM 2021 [arXiv, journal]
• M. Gańczorz Entropy Lower Bounds for Dictionary Compression CPM 2019 [conference version]