Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Efficient algorithms and representations in formal languages and automata theory.

2011/01/D/ST6/07164

Keywords:

formal languages automata efficient algorithms efficient representacions

Descriptors:

  • ST6_7: Artificial intelligence, intelligent systems, multi-agent systems

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

Number of co-investigators in the project: 5

Call: SONATA 1 - announced on 2011-03-15

Amount awarded: 500 000 PLN

Project start date (Y-m-d): 2011-12-07

Project end date (Y-m-d): 2015-06-06

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

Project status: Project settled

Equipment purchased [PL]

  1. Netbook Asus X102BA-DF010H (1 500 PLN)
  2. laptop ASUS zenbook UX31E (4 500 PLN)

Information in the final report

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