Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Wydajne algorytmy i reprezentacje w teorii języków formalnych i automatów.

2011/01/D/ST6/07164

Słowa kluczowe:

języki formalne automaty wydajne algorytmy wydajne reprezetacje

Deskryptory:

  • ST6_7: Teoretyczne podstawy informatyki, w tym informatyka kwantowa

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 Artur Jeż 

Liczba wykonawców projektu: 5

Konkurs: SONATA 1 - ogłoszony 2011-03-15

Przyznana kwota: 500 000 PLN

Rozpoczęcie projektu: 2011-12-07

Zakończenie projektu: 2015-06-06

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

Status projektu: Projekt rozliczony

Zakupiona aparatura

  1. Netbook Asus X102BA-DF010H. Za kwotę 1 500 PLN
  2. laptop ASUS zenbook UX31E. Za kwotę 4 500 PLN

Dane z raportu końcowego

  • Publikacje w czasopismach (5)
  • Teksty w publikacjach pokonferencyjnych (16)
  1. Faster Fully Compressed Pattern Matching by Recompression IF: 0,4
    Autorzy:
    Artur Jeż
    Czasopismo:
    ACM Transactions on Algorithms (rok: 2015, tom: 0,460416666666667, strony: 20:1-43), Wydawca: Association for Computing Machinery (ACM)
    Status:
    Opublikowana
    Doi:
    10.1145/2631920 - link do publikacji
  2. The Complexity of Compressed Membership Problems for Finite Automata IF: 0,452
    Autorzy:
    Artur Jeż
    Czasopismo:
    Theory of Computing Systems (rok: 2014, tom: 2,29444444444444, strony: 685-718), Wydawca: Springer US
    Status:
    Opublikowana
    Doi:
    10.1007/s00224-013-9443-6 - link do publikacji
  3. Approximate pattern matching in LZ77-compressed texts
    Autorzy:
    Travis Gagiea, Paweł Gawrychowski, Simon J.Puglisi
    Czasopismo:
    Journal of Discrete Algorithms (rok: 2015, tom: 32, strony: 64-68), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
  4. Approximation of grammar-based compression via recompression IF: 0,657
    Autorzy:
    Artur Jeż
    Czasopismo:
    Theoretical Computer Science (rok: 2015, tom: 592, strony: 115-134), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.tcs.2015.05.027 - link do publikacji
  5. Computational completeness of equations over sets of natural numbers IF: 0,604
    Autorzy:
    Artur Jeż, Alexander Okhotin
    Czasopismo:
    Information and Computation (rok: 2014, tom: 237, strony: 56-94), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.ic.2014.05.001 - link do publikacji
  1. Generating Small Automata and the Cerny Conjecture
    Autorzy:
    Andrzej Kisielewicz, Marek Szykuła
    Konferencja:
    18th International Conference on Implementation and Application of Automata (CIAA 2013) (rok: 2013, ), Wydawca: Springer
    Data:
    konferencja 16.07.2013-19.07.2013
    Status:
    Opublikowana
  2. Strong inapproximability of the shortest reset word
    Autorzy:
    Pawel Gawrychowski, Damian Straszak
    Konferencja:
    40th International Symposium on Mathematical Foundations of Computer Science (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 24-28.08.2105
    Status:
    Przyjęta do publikacji
  3. Approximation of smallest linear tree grammar
    Autorzy:
    Artur Jeż, Markus Lohrey
    Konferencja:
    STACS (rok: 2014, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 5.03.2014-8.03.2014
    Status:
    Opublikowana
  4. Discovering Hidden Repetitions in Words
    Autorzy:
    Paweł Gawrychowski, Florin Manea, Dirk Nowotka
    Konferencja:
    9th Conference on Computability in Europe: The Nature of Computation. Logic, Algorithms, Applications (CiE 2013) (rok: 2013, ), Wydawca: Springer
    Data:
    konferencja 1.06.2013-5.06.2013
    Status:
    Opublikowana
  5. Faster Fully Compressed Pattern Matching by Recompression
    Autorzy:
    Artur Jeż
    Konferencja:
    39th International Colloquium on Automata, Languages, and Programming (ICALP 2012) (rok: 2012, ), Wydawca: Springer
    Data:
    konferencja 9.07.2012-13.07.2012
    Status:
    Opublikowana
  6. Finding Pseudo-repetitions
    Autorzy:
    Paweł Gawrychowski, Florin Manea, Robert Mercas, Dirk Nowotka, Catalin Tiseanu
    Konferencja:
    30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) (rok: 2013, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 27.02.2013-03.03.2013
    Status:
    Opublikowana
  7. Recompression: Word Equations and Beyond
    Autorzy:
    Artur Jeż
    Konferencja:
    17th International Conference on Developments in Language Theory (DLT 2013) (rok: 2013, ), Wydawca: Springer
    Data:
    konferencja 18.06.2013-21.06.2013
    Status:
    Opublikowana
  8. Hyper-minimization for Deterministic Tree Automata
    Autorzy:
    Artur Jeż, Andreas Maletti
    Konferencja:
    17th International Conference on Implementation and Application of Automata (CIAA 2012) (rok: 2012, ), Wydawca: Springer
    Data:
    konferencja 17.07.2012-20.07.2012
    Status:
    Opublikowana
  9. Which Finitely Ambiguous Automata Recognize Finitely Sequential Functions?
    Autorzy:
    Sebastian Bala
    Konferencja:
    38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013) (rok: 2013, ), Wydawca: Springer
    Data:
    konferencja 26.08.2013-30.08.2013
    Status:
    Opublikowana
  10. Beating O(nm) in Approximate LZW-Compressed Pattern Matching
    Autorzy:
    Paweł Gawrychowski, Damian Straszak
    Konferencja:
    24th International Symposium on Algorithms and Computation (ISAAC 2013) (rok: 2013, ), Wydawca: Springer
    Data:
    konferencja 16.12.2013-18.12.2013
    Status:
    Opublikowana
  11. Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)
    Autorzy:
    Artur Jeż
    Konferencja:
    29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) (rok: 2012, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 29.03.2012-3.03.2012
    Status:
    Opublikowana
  12. Euclidean TSP with Few Inner Points in Linear Space
    Autorzy:
    Paweł Gawrychowski, Damian Rusak
    Konferencja:
    25th International Symposium on Algorithms and Computation (ISAAC 2014) (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 15-17.12.2014
    Status:
    Opublikowana
  13. Recompression: a simple and powerful technique for word equations
    Autorzy:
    Artur Jeż
    Konferencja:
    30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) (rok: 2013, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 27.02.2013-03.03.2013
    Status:
    Opublikowana
  14. Testing Generalised Freeness of Words
    Autorzy:
    Paweł Gawrychowski, Florin Manea, Dirk Nowotka
    Konferencja:
    STACS (rok: 2014, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 5.03.2014-8.03.2014
    Status:
    Opublikowana
  15. Unambiguous Conjunctive Grammars over a One-Letter Alphabet
    Autorzy:
    Artur Jeż, Alexander Okhotin
    Konferencja:
    17th International Conference Developments in Language Theory (DLT 2013) (rok: 2013, ), Wydawca: Springer
    Data:
    konferencja 18.06.2013-21.06.2013
    Status:
    Opublikowana
  16. Approximation of Grammar-Based Compression via Recompression
    Autorzy:
    Artur Jeż
    Konferencja:
    24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013) (rok: 2013, ), Wydawca: Springer
    Data:
    konferencja 17.06.2013-19.06.2013
    Status:
    Opublikowana