Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Kompresja, logika, języki formalne: nowe podejścia łączące różne dziedziny.

2014/15/B/ST6/00615

Słowa kluczowe:

grammar compression logic formal languages

Deskryptory:

  • 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 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Uniwersytet Wrocławski, Wydział Matematyki i Informatyki

woj. dolnośląskie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr hab. Artur Jeż 

Liczba wykonawców projektu: 5

Konkurs: OPUS 8 - ogłoszony 2014-09-15

Przyznana kwota: 646 000 PLN

Rozpoczęcie projektu: 2015-07-22

Zakończenie projektu: 2018-12-21

Planowany czas trwania projektu: 36 miesięcy (z wniosku)

Status projektu: Projekt rozliczony

Zakupiona aparatura

  1. Laptop. Za kwotę 9 000 PLN

Dane z raportu końcowego

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