Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Compression, logic, formal langauges: new approaches unifying different areas.

2014/15/B/ST6/00615

Keywords:

kompresja gramatykowa logika języki formalne

Descriptors:

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

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: 5

Call: OPUS 8 - announced on 2014-09-15

Amount awarded: 646 000 PLN

Project start date (Y-m-d): 2015-07-22

Project end date (Y-m-d): 2018-12-21

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

Project status: Project settled

Equipment purchased [PL]

  1. Laptop (9 000 PLN)

Information in the final report

  • Publication in academic press/journals (9)
  • Articles in post-conference publications (12)
  1. Approximation of smallest linear tree grammar
    Authors:
    Artur Jeż, Markus Lohrey
    Academic press:
    Information and Computation (rok: 2016, tom: 251, strony: 215–251), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2016.09.007 - link to the publication
  2. Complexity of bifix-free regular languages
    Authors:
    Robert Ferens, Marek Szykuła
    Academic press:
    Theoretical Computer Science (rok: 2019, tom: 787, strony: 14–27), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2018.09.016 - link to the publication
  3. Syntactic complexity of suffix-free languages
    Authors:
    Janusz A. Brzozowski, Marek Szykuła
    Academic press:
    Information and Computation (rok: 2018, tom: 10,7930555555556, strony: 174–190), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2017.08.014 - link to the publication
  4. Algebraic synchronization criterion and computing reset words
    Authors:
    Mikhail V. Berlinkov, Marek Szykuła
    Academic press:
    Information Sciences 369:718--730, (rok: 2016, tom: 369, strony: 718–730), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ins.2016.07.049 - link to the publication
  5. Complexity of suffix-free regular languages
    Authors:
    Janusz Brzozowski, Marek Szykuła
    Academic press:
    Journal of Computer and System Sciences (rok: 2017, tom: 89, strony: 270–287), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2017.05.011 - link to the publication
  6. Deciding Context Unification
    Authors:
    Artur Jeż
    Academic press:
    Journal of the ACM (rok: 2019, tom: 2,75416666666667, strony: 39:1–39:45), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3356904 - link to the publication
  7. Unambiguous conjunctive grammars over a one-symbol alphabet
    Authors:
    Artur Jeż, Alexander Okhotin
    Academic press:
    Theoretical Computer Science (rok: 2017, tom: 665, strony: 13–39), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2016.12.009 - link to the publication
  8. Finding all solutions of equations in free groups and monoids with involution
    Authors:
    Volker Diekert, Artur Jeż, Wojciech Plandowski
    Academic press:
    Information and Computation (rok: 2016, tom: 251, strony: 262–286), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2016.09.009 - link to the publication
  9. Syntactic complexity of bifix-free regular languages
    Authors:
    Marek Szykuła, John Wittnebel
    Academic press:
    Theoretical Computer Science (rok: 2019, tom: 787, strony: 45-76), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2018.12.025 - link to the publication
  1. Complexity of Preimage Problems for Deterministic Finite Automata
    Authors:
    Mikhail V. Berlinkov, Robert Ferens, Marek Szykuła
    Conference:
    43rd International Symposium on Mathematical Foundations of Computer Science (MFCS) (rok: 2018, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 27–31.08.2018
    Status:
    Published
    DOI:
    link to the publication
  2. Improvements on Re-Pair Grammar Compressor
    Authors:
    Michał Gańczorz, Artur Jeż
    Conference:
    Data Compression Conference (DCC) (rok: 2017, ), Wydawca: IEEE
    Data:
    konferencja 4–7.04.2017
    Status:
    Published
    DOI:
    link to the publication
  3. LZ77 Factorisation of Trees
    Authors:
    Paweł Gawrychowski, Artur Jeż
    Conference:
    Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (rok: 2016, ), Wydawca: Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 15–20.12.2016
    Status:
    Published
    DOI:
    link to the publication
  4. Syntactic Complexity of Bifix-Free Languages
    Authors:
    Marek Szykuła, John Wittnebel
    Conference:
    International Conference on Implementation and Application of Automata (CIAA) (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 27–30.06.2017
    Status:
    Published
    DOI:
    link to the publication
  5. Finding Short Synchronizing Words for Prefix Codes
    Authors:
    Marek Szykuła, Andrew Ryzhikov
    Conference:
    43rd International Symposium on Mathematical Foundations of Computer Science (MFCS) (rok: 2018, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 27–31.08.2018
    Status:
    Published
    DOI:
    link to the publication
  6. Word Equations in Nondeterministic Linear Space
    Authors:
    Artur Jeż
    Conference:
    International Colloquium on Automata, Languages, and Programming (ICALP B) (rok: 2017, ), Wydawca: Schloss Dagstuhl–Leibniz- Zentrum fuer Informatik
    Data:
    konferencja 10–14.07.2017
    Status:
    Published
    DOI:
    link to the publication
  7. Attainable Values of Reset Thresholds
    Authors:
    Michalina Dżyga, Robert Ferens, Vladimir V. Gusev, Marek Szykula
    Conference:
    International Symposium on Mathematical Foundations of Computer Science (MFCS) (rok: 2017, ), Wydawca: Schloss Dagstuhl--Leibniz- Zentrum fuer Informatik
    Data:
    konferencja 21–25.08.2017
    Status:
    Published
    DOI:
    link to the publication
  8. Slowing Down Top Trees for Better Worst-Case Compression
    Authors:
    Bartłomiej Dudek, Paweł Gawrychowski
    Conference:
    Annual Symposium on Combinatorial Pattern Matching (CPM) (rok: 2018, ), Wydawca: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 2–4.07.2018
    Status:
    Published
    DOI:
    link to the publication
  9. Edit Distance with Block Operations
    Authors:
    Michał Gańczorz, Paweł Gawrychowski, Artur Jeż, Tomasz Kociumaka
    Conference:
    Annual European Symposium on Algorithms (ESA) (rok: 2018, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 20–22.08.2018
    Status:
    Published
    DOI:
    link to the publication
  10. Complexity of Bifix-Free Regular Languages
    Authors:
    Robert Ferens, Marek Szykuła
    Conference:
    International Conference on Implementation and Application of Automata (CIAA) (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 27–30.06.2017
    Status:
    Published
    DOI:
    link to the publication
  11. On the State Complexity of the Shuffle of Regular Languages
    Authors:
    Janusz A. Brzozowski, Galina Jirásková, Bo Liu, Aayush Rajasekaran, Marek Szykuła.
    Conference:
    Descriptional Complexity of Formal Systems (DCFS) (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 6-8.07.2016
    Status:
    Published
    DOI:
    link to the publication
  12. State Complexity of Overlap Assembly
    Authors:
    Janusz A. Brzozowski, Lila Kari, Bai Li, Marek Szykuła
    Conference:
    International Conference on Implementation and Application of Automata (CIAA) (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 30.07–2.08.2018
    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