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
Principal investigator (from the host institution)
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]
- Laptop. Cost: 9 000 PLN
Information in the final report
Publication in academic press/journals (9)
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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)
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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