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

2014/15/B/ST6/00615

Keywords

Descriptors

  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier

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

Voivodeship: 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
2015-07-22
Project end date
2018-12-21
Project duration
41 months (the same as in the proposal)
Project status
Project settled

Equipment purchased [PL]

  1. Laptop. Cost: 9 000 PLN

Information in the final report

Publication in academic press/journals (9)

  1. Approximation of smallest linear tree grammar

    Authors:
    Artur Jeż, Markus Lohrey
    Academic press:
    Information and Computation (year: 2016, volume: 251, pages: 215–251), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2016.09.007 – link to the publication
  2. Complexity of suffix-free regular languages

    Authors:
    Janusz Brzozowski, Marek Szykuła
    Academic press:
    Journal of Computer and System Sciences (year: 2017, volume: 89, pages: 270–287), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2017.05.011 – link to the publication
  3. Finding all solutions of equations in free groups and monoids with involution

    Authors:
    Volker Diekert, Artur Jeż, Wojciech Plandowski
    Academic press:
    Information and Computation (year: 2016, volume: 251, pages: 262–286), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2016.09.009 – link to the publication
  4. Complexity of bifix-free regular languages

    Authors:
    Robert Ferens, Marek Szykuła
    Academic press:
    Theoretical Computer Science (year: 2019, volume: 787, pages: 14–27), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2018.09.016 – link to the publication
  5. Unambiguous conjunctive grammars over a one-symbol alphabet

    Authors:
    Artur Jeż, Alexander Okhotin
    Academic press:
    Theoretical Computer Science (year: 2017, volume: 665, pages: 13–39), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2016.12.009 – link to the publication
  6. Algebraic synchronization criterion and computing reset words

    Authors:
    Mikhail V. Berlinkov, Marek Szykuła
    Academic press:
    Information Sciences 369:718--730, (year: 2016, volume: 369, pages: 718–730), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ins.2016.07.049 – link to the publication
  7. Syntactic complexity of suffix-free languages

    Authors:
    Janusz A. Brzozowski, Marek Szykuła
    Academic press:
    Information and Computation (year: 2018, volume: 10,7930555555556, pages: 174–190), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2017.08.014 – link to the publication
  8. Deciding Context Unification

    Authors:
    Artur Jeż
    Academic press:
    Journal of the ACM (year: 2019, volume: 2,75416666666667, pages: 39:1–39:45), Publisher: ACM
    Status:
    Published
    DOI:
    10.1145/3356904 – link to the publication
  9. Syntactic complexity of bifix-free regular languages

    Authors:
    Marek Szykuła, John Wittnebel
    Academic press:
    Theoretical Computer Science (year: 2019, volume: 787, pages: 45-76), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2018.12.025 – link to the publication

Articles in post-conference publications (12)

  1. Complexity of Bifix-Free Regular Languages

    Authors:
    Robert Ferens, Marek Szykuła
    Conference:
    International Conference on Implementation and Application of Automata (CIAA) (year: 2017, pages: 76–88), Publisher: Springer
    Date:
    conference 27–30.06.2017
    Status:
    Published
    DOI:
    link to the publication
  2. Syntactic Complexity of Bifix-Free Languages

    Authors:
    Marek Szykuła, John Wittnebel
    Conference:
    International Conference on Implementation and Application of Automata (CIAA) (year: 2017, pages: 201–212), Publisher: Springer
    Date:
    conference 27–30.06.2017
    Status:
    Published
    DOI:
    link to the publication
  3. 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) (year: 2016, pages: 73-86), Publisher: Springer
    Date:
    conference 6-8.07.2016
    Status:
    Published
    DOI:
    link to the publication
  4. LZ77 Factorisation of Trees

    Authors:
    Paweł Gawrychowski, Artur Jeż
    Conference:
    Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (year: 2016, pages: 35:1–35:15), Publisher: Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik
    Date:
    conference 15–20.12.2016
    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) (year: 2018, pages: 21:1–1:14), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 27–31.08.2018
    Status:
    Published
    DOI:
    link to the publication
  6. Slowing Down Top Trees for Better Worst-Case Compression

    Authors:
    Bartłomiej Dudek, Paweł Gawrychowski
    Conference:
    Annual Symposium on Combinatorial Pattern Matching (CPM) (year: 2018, pages: 16:1–16:8), Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
    Date:
    conference 2–4.07.2018
    Status:
    Published
    DOI:
    link to the publication
  7. 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) (year: 2018, pages: 109–120), Publisher: Springer
    Date:
    conference 30.07–2.08.2018
    Status:
    Published
    DOI:
    link to the publication
  8. 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) (year: 2018, pages: 32:1–32:14), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 27–31.08.2018
    Status:
    Published
    DOI:
    link to the publication
  9. 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) (year: 2017, pages: 40:1–40:14), Publisher: Schloss Dagstuhl--Leibniz- Zentrum fuer Informatik
    Date:
    conference 21–25.08.2017
    Status:
    Published
    DOI:
    link to the publication
  10. Improvements on Re-Pair Grammar Compressor

    Authors:
    Michał Gańczorz, Artur Jeż
    Conference:
    Data Compression Conference (DCC) (year: 2017, pages: 181–190), Publisher: IEEE
    Date:
    conference 4–7.04.2017
    Status:
    Published
    DOI:
    link to the publication
  11. Word Equations in Nondeterministic Linear Space

    Authors:
    Artur Jeż
    Conference:
    International Colloquium on Automata, Languages, and Programming (ICALP B) (year: 2017, pages: 95:1–95:13), Publisher: Schloss Dagstuhl–Leibniz- Zentrum fuer Informatik
    Date:
    conference 10–14.07.2017
    Status:
    Published
    DOI:
    link to the publication
  12. Edit Distance with Block Operations

    Authors:
    Michał Gańczorz, Paweł Gawrychowski, Artur Jeż, Tomasz Kociumaka
    Conference:
    Annual European Symposium on Algorithms (ESA) (year: 2018, pages: 33:1–33:14), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 20–22.08.2018
    Status:
    Published
    DOI:
    link to the publication

« New search

Graphic design and implementation: Jakub Piotrowski