Zmiana języka

Projects search

Efficient algorithms and representations in formal languages and automata theory.

2011/01/D/ST6/07164

Keywords

Descriptors

  • ST6_7: Teoretyczne podstawy informatyki, w tym informatyka kwantowa

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 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
2011-12-07
Project end date
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. Cost: 1 500 PLN
  2. laptop ASUS zenbook UX31E. Cost: 4 500 PLN

Information in the final report

Publication in academic press/journals (5)

  1. Approximation of grammar-based compression via recompression

    Authors:
    Artur Jeż
    Academic press:
    Theoretical Computer Science (year: 2015, volume: 592, pages: 115-134), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2015.05.027 – link to the publication

  2. Computational completeness of equations over sets of natural numbers

    Authors:
    Artur Jeż, Alexander Okhotin
    Academic press:
    Information and Computation (year: 2014, volume: 237, pages: 56-94), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2014.05.001 – link to the publication

  3. The Complexity of Compressed Membership Problems for Finite Automata

    Authors:
    Artur Jeż
    Academic press:
    Theory of Computing Systems (year: 2014, volume: 2,29444444444444, pages: 685-718), Publisher: Springer US
    Status:
    Published
    DOI:
    10.1007/s00224-013-9443-6 – link to the publication

  4. Approximate pattern matching in LZ77-compressed texts

    Authors:
    Travis Gagiea, Paweł Gawrychowski, Simon J.Puglisi
    Academic press:
    Journal of Discrete Algorithms (year: 2015, volume: 32, pages: 64-68), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jda.2014.10.003 – link to the publication

  5. Faster Fully Compressed Pattern Matching by Recompression

    Authors:
    Artur Jeż
    Academic press:
    ACM Transactions on Algorithms (year: 2015, volume: 0,460416666666667, pages: 20:1-43), Publisher: Association for Computing Machinery (ACM)
    Status:
    Published
    DOI:
    10.1145/2631920 – link to the publication

Articles in post-conference publications (16)

  1. Approximation of smallest linear tree grammar

    Authors:
    Artur Jeż, Markus Lohrey
    Conference:
    STACS (year: 2014, pages: 445-457), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 5.03.2014-8.03.2014
    Status:
    Published
    DOI:
    link to the publication

  2. Euclidean TSP with Few Inner Points in Linear Space

    Authors:
    Paweł Gawrychowski, Damian Rusak
    Conference:
    25th International Symposium on Algorithms and Computation (ISAAC 2014) (year: 2014, pages: 701-713), Publisher: Springer
    Date:
    conference 15-17.12.2014
    Status:
    Published

  3. Testing Generalised Freeness of Words

    Authors:
    Paweł Gawrychowski, Florin Manea, Dirk Nowotka
    Conference:
    STACS (year: 2014, pages: 337-349), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Date:
    conference 5.03.2014-8.03.2014
    Status:
    Published
    DOI:
    link to the publication

  4. 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) (year: 2012, pages: 136-147), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 29.03.2012-3.03.2012
    Status:
    Published
    DOI:
    link to the publication

  5. Hyper-minimization for Deterministic Tree Automata

    Authors:
    Artur Jeż, Andreas Maletti
    Conference:
    17th International Conference on Implementation and Application of Automata (CIAA 2012) (year: 2012, pages: 217-228), Publisher: Springer
    Date:
    conference 17.07.2012-20.07.2012
    Status:
    Published
    DOI:
    link to the publication

  6. Faster Fully Compressed Pattern Matching by Recompression

    Authors:
    Artur Jeż
    Conference:
    39th International Colloquium on Automata, Languages, and Programming (ICALP 2012) (year: 2012, pages: 533-544), Publisher: Springer
    Date:
    conference 9.07.2012-13.07.2012
    Status:
    Published
    DOI:
    link to the publication

  7. 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) (year: 2013, pages: 257-268), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 27.02.2013-03.03.2013
    Status:
    Published
    DOI:
    link to the publication

  8. Unambiguous Conjunctive Grammars over a One-Letter Alphabet

    Authors:
    Artur Jeż, Alexander Okhotin
    Conference:
    17th International Conference Developments in Language Theory (DLT 2013) (year: 2013, pages: 277-288), Publisher: Springer
    Date:
    conference 18.06.2013-21.06.2013
    Status:
    Published
    DOI:
    link to the publication

  9. Recompression: Word Equations and Beyond

    Authors:
    Artur Jeż
    Conference:
    17th International Conference on Developments in Language Theory (DLT 2013) (year: 2013, pages: 46382), Publisher: Springer
    Date:
    conference 18.06.2013-21.06.2013
    Status:
    Published
    DOI:
    link to the publication

  10. Which Finitely Ambiguous Automata Recognize Finitely Sequential Functions?

    Authors:
    Sebastian Bala
    Conference:
    38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013) (year: 2013, pages: 86-97), Publisher: Springer
    Date:
    conference 26.08.2013-30.08.2013
    Status:
    Published
    DOI:
    link to the publication

  11. 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) (year: 2013, pages: 340-348), Publisher: Springer
    Date:
    conference 16.07.2013-19.07.2013
    Status:
    Published
    DOI:
    link to the publication

  12. Recompression: a simple and powerful technique for word equations

    Authors:
    Artur Jeż
    Conference:
    30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) (year: 2013, pages: 233-244), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference 27.02.2013-03.03.2013
    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) (year: 2013, pages: 78-88), Publisher: Springer
    Date:
    conference 16.12.2013-18.12.2013
    Status:
    Published
    DOI:
    link to the publication

  14. Approximation of Grammar-Based Compression via Recompression

    Authors:
    Artur Jeż
    Conference:
    24th Annual Symposium on Combinatorial Pattern Matching (CPM 2013) (year: 2013, pages: 165-176), Publisher: Springer
    Date:
    conference 17.06.2013-19.06.2013
    Status:
    Published
    DOI:
    link to the publication

  15. 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) (year: 2013, pages: 210-219), Publisher: Springer
    Date:
    conference 1.06.2013-5.06.2013
    Status:
    Published
    DOI:
    link to the publication

  16. Strong inapproximability of the shortest reset word

    Authors:
    Pawel Gawrychowski, Damian Straszak
    Conference:
    40th International Symposium on Mathematical Foundations of Computer Science (year: 2015), Publisher: Springer
    Status:
    Accepted for publication

« New search

Graphic design and implementation: Jakub Piotrowski