Menu
  • Publikacje Zakładu Złożoności Obliczeniowej i Analizy Algorytmów w roku 2017

    1. M. Karpiński, Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete, Theoretical Computer Science. - Vol. 659 (2017), s. 88-94. (http://dx.doi.org/10.1016/j.tcs.2016.10.011)
    2. M. Ganardi, D. Hucke, A. Jeż, M. Lohrey, E. Noeth, Constructing small tree grammars and small circuits for formulas, Journal of Computer and System Sciences. - Vol. 86 (2017), s. 136-158. (https://doi.org/10.1016/j.jcss.2016.12.007)
    3. M. Gańczorz, A. Jeż, Improvements on Re-Pair grammar compressor, // W: DCC 2017 : 2017 Data Compression Conference : 4-7 April 2017, Snowbird, Utah, USA : proceedings / Ali Bilgin, Michael W. Marcellin, Joan Serra-Sagrista, James A. Storer (eds.). - Piscataway : IEEE, 2017. - (Proceedings). - S. 181-190. (http://dx.doi.org/10.1109/DCC.2017.52)
    4. A. Jeż, Recompression: new approach to word equations and context unification (Invited Talk), // W: 34th Symposium on Theoretical Aspects of Computer Science : STACS 2017, March 8-11, 2017, Hannover, Germany / Heribert Vollmer, Brigitte Vallée (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. - ( LIPIcs - Leibniz International Proceedings in Informatics ; 66). - S. 2-1-2-3. (http://dx.doi.org/10.4230/LIPIcs.STACS.2017.2)
    5. A. Jeż, A. Okhotin, Unambiguous conjunctive grammars over a one-symbol alphabet, Theoretical Computer Science. - Vol. 665 (2017), s. 13-39. (https://doi.org/10.1016/j.tcs.2016.12.009)
    6. A. Jeż, Word equations in nondeterministic linear space // W: 44th International Colloquium on Automata, Languages, and Programming : ICALP 2017, Warsaw, Poland, July 10-14, 2017 / Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, Anca Muscholl (eds.). - Saarbrücken/Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. - (Leibniz International Proceedings in Informatics (LIPIcs) ; 80). - S. 95-1-95-13. (http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.95)
    7. J. Kowalski, A. Roman, A new evolutionary algorithm for synchronization, // W: Applications of Evolutionary Computation : 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part I / Giovanni Squillero, Kevin Sim (eds.). - Cham : Springer International Publishing - Springer, 2017. - (Lecture Notes in Computer Science ; 10199).- S. 620-635. (http://dx.doi.org/10.1007/978-3-319-55849-3_40)
    8. L. Gąsieniec, D. Hamilton, R. Martin, P.G. Spirakis, G. Stachowiak, Deterministic population protocols for exact majority and plurality, // W: 20th International Conference On Principles Of Distributed Systems (OPODIS-16), December 13-16th, 2016, Madrid, Spain / Panagiota Fatourou, Ernesto Jiménez, Fernando Pedone (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. - (LIPIcs - Leibniz Internation Proceedings in Informatics ; 70).- S. 14-1-14-14. (http://dx.doi.org/10.4230/LIPIcs.OPODIS.2016.14)
    9. V.V. Gusev, E. Pribavkina, M. Szykuła, Around the road coloring theorem, // W: Proceedings of the Fourth Russian-Finnish Symposium on Discrete Mathematics Organized in Turku on 16.-19.5.2017 / Juhani Karhumäki, Yuri Matiyasevich, Aleksi Saarela (eds.). - Turku : Turku Centre for Computer Science, 2017. - (TUCS Lecture Notes ; 26). - S. 52-56.
    10. R. Ferens, M. Szykuła, Complexity of bifix-free regular languages, // W: Implementation and Application of Automata : 22nd International Conference, CIAA 2017, Marne-la-Vallée, France, June 27-30, 2017, Proceedings / Arnaud Carayol, Cyril Nicaud (eds.). - Cham : Springer, 2017. - (Lecture Notes in Computer Science ; 10329). - S. 76-88. (http://dx.doi.org/10.1007/978-3-319-60134-2_7)
    11. J.A. Brzozowski, M. Szykuła, Complexity of suffix-free regular languages, Journal of Computer and System Sciences. - Vol. 89 (2017), s. 270-287. (http://dx.doi.org/10.1016/j.jcss.2017.05.011)
    12. M. Szykuła, J. Wittnebel, Syntactic complexity of bifix-free languages, // W: Implementation and Application of Automata : 22nd International Conference, CIAA 2017, Marne-la-Vallée, France, June 27-30, 2017, Proceedings / Arnaud Carayol, Cyril Nicaud (eds.). - Cham : Springer, 2017. - (Lecture Notes in Computer Science ; 10329). - S. 201-212. (http://dx.doi.org/10.1007/978-3-319-60134-2_17)
  • Publikacje Zakładu Złożoności Obliczeniowej i Analizy Algorytmów w roku 2016

    1. A. Jeż, One-variable word equations in linear time, Algorithmica. - Vol. 74, iss. 1 (2016), s. 1-48. (http://dx.doi.org/10.1007/s00453-014-9931-3)
    2. A. Jeż, A really simple approximation of smallest grammar, Theoretical Computer Science. - Vol. 616 (2016), s. 141-150. (http://dx.doi.org/10.1016/j.tcs.2015.12.032)
    3. A. Jeż, A. Okhotin, Equations over sets of integers with addition only, Journal of Computer and System Sciences. - Vol. 82, Iss. 6 (2016), s. 1007-1019. (http://dx.doi.org/10.1016/j.jcss.2016.02.003)
    4. A. Jeż, A. Okhotin, Least and greatest solutions of equations over sets of integers, Theoretical Computer Science. - Vol. 619 (2016), s. 68-86. (http://dx.doi.org/10.1016/j.tcs.2016.01.013)
    5. A. Jeż, Recompression: a simple and powerful technique for word equations, Journal of the ACM. - Vol. 63, iss. 1 (2016), nr art. 4. (http://dx.doi.org/10.1145/2743014)
    6. V. Diekert, A. Jeż, M. Kufleitner, Solutions of word equations over partially commutative structures, W: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) / Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (eds.). - Wadern : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. - (Leibniz International Proceedings in Informatics (LIPIcs) ; 55). - S. 127:1-127:14. (http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.127)
    7. A. Kisielewicz, J. Kowalski, M. Szykuła, Experiments with synchronizing automata, W: Implementation and Application of Automata : 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings / Yo-Sub Han, Kai Salomaa (eds.). - Cham : Springer International Publishing - Springer, 2016. - (Lecture Notes in Computer Science ; 9705).- S. 176-188. (http://dx.doi.org/10.1007/978-3-319-40946-7_15)
    8. J. Kowalski, A. Kisielewicz, Towards a real-time game description language, W: ICAART 2016 : 8th International Conference on Agents and Artificial Intelligence, February 24-26, 2016, in Rome, Italy, Proceedings, Vol.2 / Jaap van den Herik, Joaquim Filipe (eds.). - [Setúbal] : SCITEPRESS , 2016. - S. 494-499. (http://dx.doi.org/10.5220/0005816904940499)
    9. M. Piotrów, Faster merging networks with a small constant period, Theoretical Computer Science. - Vol. 640 (2016) , s. 20-40. (http://dx.doi.org/10.1016/j.tcs.2016.05.038)
    10. M. V. Berlinkov, M. Szykuła, Algebraic synchronization criterion and computing reset words, Information Sciences. - Vol. 369 (2016), s. 718-730. (http://dx.doi.org/10.1016/j.ins.2016.07.049)
    11. M. Szykuła, V. Vorel, An extremal series of eulerian synchronizing automata, W: Developments in Language Theory : 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings / Srečko Brlek, Christophe Reutenauer (eds.). - Berlin, Heidelberg : Springer , 2016. - (Lecture Notes in Computer Science ; 9840).- S. 380-392. (http://dx.doi.org/10.1007/978-3-662-53132-7_31)
    12. J. Kowalski, M. Szykuła, Evolving chess-like games using relative algorithm performance profiles, W: Applications of Evolutionary Computation : 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 -- April 1, 2016, Proceedings, Part I / Giovanni Squillero, Paolo Burelli (eds.). - Cham : Springer International Publishing, 2016. - (Lecture Notes in Computer Science ; 9597).- S. 574-589. (http://dx.doi.org/10.1007/978-3-319-31204-0_37)
    13. J. Brzozowski, G. Jirásková, B. Liu, A. Rajasekaran, M. Szykuła, W: Descriptional Complexity of Formal Systems : 18th IFIP WG 1.2 International Conference, DCFS 2016, Bucharest, Romania, July 5-8, 2016. Proceedings / Cezar Câmpeanu, Florin Manea, Jeffrey Shallit (eds.). - Cham : Springer International Publishing - Springer, 2016. - (Lecture Notes in Computer Science ; 9777).- S. 73-86. (http://dx.doi.org/10.1007/978-3-319-41114-9_6)
    14. P. Gawrychowski, A. Jeż, LZ77 factorisation of trees, W: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) / Akash Lal, S. Akshay, Saket Saurabh, Sandeep Sen (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. - (LIPIcs - Leibniz Internation Proceedings in Informatics ; 65).- S. 35:1-35:15. (http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.35)
    15. T. Jurdziński, D. R. Kowalski, Wake-up problem in multi-hop radio networks, W: Encyclopedia of Algorithms / Ming-Yang Kao (ed.). - New York : Springer, 2016. - S. 2352-2354. (http://dx.doi.org/10.1007/978-1-4939-2864-4_536)
    16. J. Brzozowski, G. Jirásková, B. Liu, A. Rajasekaran, M. Szykuła, On the state complexity of the shuffle of regular languages, W: Descriptional Complexity of Formal Systems : 18th IFIP WG 1.2 International Conference, DCFS 2016, Bucharest, Romania, July 5-8, 2016. Proceedings / Cezar Câmpeanu, Florin Manea, Jeffrey Shallit (eds.). - Cham : Springer International Publishing - Springer, 2016. - (Lecture Notes in Computer Science ; 9777).- S. 73-86. (http://dx.doi.org/10.1007/978-3-319-41114-9_6)
  • Publikacje Zakładu Złożoności Obliczeniowej i Algorytmów w roku 2015

    1. A. Jeż, Faster fully compressed pattern matching by recompression, ACM Transactions on Algorithms. - Vol. 11, iss.3 (2015), s. article no. 20. (http://dx.doi.org/10.1145/2631920).
    2. M. Bieńkowski, J. Byrka, T. Jurdziński, K.Chrobak, D. R. Kowalski, Provable fairness for TDMA scheduling, IEEE Conference on Computer Communications, INFOCOM 2015, Kowloon, Hong Kong, April 26 - May 1, 2015, Proceedings. - Piscataway : IEEE, 2015.- S. 1320-1327. (http://dx.doi.org/10.1109/INFOCOM.2015.7218508).
    3. A. Jeż, Approximation of grammar-based compression via recompression, Theoretical Computer Science. - Vol. 592 (2015), s. 115-134. (http://dx.doi.org/10.1016/j.tcs.2015.05.027).
    4. A. Kisielewicz, J. Kowalski, M. Szykuła, Computing the shortest reset words of synchronizing automata, Journal of Combinatorial Optimization. - Vol. 29, iss. 1 (2015), s. 88-124. (http://dx.doi.org/10.1007/s10878-013-9682-0).
    5. M. Karpiński, M. Piotrów, Smaller selection networks for cardinality constraints encoding, Principles and Practice of Constraint Programming : 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015, Proceedings / Gilles Pesant (ed.). - Cham : Springer International Publishing , 2015. - (Lecture Notes in Computer Science ; 9255).- S. 210-225. (http://dx.doi.org/10.1007/978-3-319-23219-5_16).
    6. A. Kisielewicz, M. Szykuła, Synchronizing automata with extremal properties, Mathematical Foundations of Computer Science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I / Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella (eds.). - Berlin, Heidelberg : Springer Berlin, 2015. - (Lecture Notes in Computer Science ; 9234). - S. 331-343. (http://dx.doi.org/10.1007/978-3-662-48057-1_26).
    7. M. Berlinkov, M. Szykuła, Algebraic synchronization criterion and computing reset words, Mathematical Foundations of Computer Science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I / Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella (eds.). - Berlin, Heidelberg : Springer Berlin, 2015. - (Lecture Notes in Computer Science ; 9234).- S. 103-115. (http://dx.doi.org/10.1007/978-3-662-48057-1_8).
    8. M. Szykuła, Checking whether an automaton is monotonic is NP-complete, Implementation and Application of Automata : 20th International Conference, CIAA 2015, Umea, Sweden, August 18-21, 2015, Proceedings / Frank Drewes (ed.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 9223).- S. 279-291. (http://dx.doi.org/10.1007/978-3-319-22360-5).
    9. J. Brzozowski, M. Szykuła, Complexity of suffix-free regular languages, Fundamentals of Computation Theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings / Adrian Kosowski, Igor Walukiewicz (eds.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 9210).- S. 146-159. (http://dx.doi.org/10.1007/978-3-319-22177-9_12).
    10. V. V. Gusev, M. Szykuła, On the number of synchronizing colorings of digraphs, Implementation and Application of Automata : 20th International Conference, CIAA 2015, Umea, Sweden, August 18-21, 2015, Proceedings / Frank Drewes (ed.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 9223).- S. 127-139. (http://dx.doi.org/10.1007/978-3-319-22360-5_11).
    11. J. Brzozowski, M. Szykuła, Upper bound on syntactic complexity of suffix-free languages, Descriptional Complexity of Formal Systems : 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings / Jeffrey Shallit, Alexander Okhotin (eds.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 9118).- S. 33-45. (http://dx.doi.org/10.1007/978-3-319-19225-3_3).
    12. A. Kisielewicz, J. Kowalski, Testing general game players against a Simplified Boardgames player using temporal-difference learning, 2015 IEEE Congress on Evolutionary Computation, (CEC 2015), Sendai, Japan, May 25-28, 2015, Proceedings. - Piscataway : Institute of Electrical and Electronics Engineers, 2015. - S. 1466-1473. (http://dx.doi.org/10.1109/CEC.2015.7257061).
    13. T. Jurdziński, G. Stachowiak, Deterministic symmetry breaking in ring networks, 2015 IEEE 35th International Conference on Distributed Computing Systems (ICDCS 2015) ; Columbus, Ohio, USA, 29 June - 2 July 2015. - Piscataway, NJ : IEEE, 2015.- S. 517-526. (http://dx.doi.org/10.1109/ICDCS.2015.59).
    14. T. Jurdziński, M. Różański, G. Stachowiak, On setting-up asynchronous ad hoc wireless networks, 2015 IEEE Conference on Computer Communications (INFOCOM 2015) : Kowloon, Hong Kong, 26 April - 1 May 2015. - Piscataway, NJ : IEEE, 2015. - S. 2191 - 2199. (http://dx.doi.org/10.1109/INFOCOM.2015.7218605).
    15. T. Jurdziński, G. Stachowiak, The cost of synchronizing multiple-access channels, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing - PODC '15 . - New York : ACM , 2015.- S. 421-430. (http://dx.doi.org/10.1145/2767386.2767439).
    16. T. Jurdziński, D. R. Kowalski, K. Loryś, Online packet scheduling under adversarial jamming, Approximation and Online Algorithms : 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014. - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 8952). - S. 193-206. (http://dx.doi.org/10.1007/978-3-319-18263-6_17).
    17. A. Roman, M. Szykuła, Forward and backward synchronizing algorithms, Expert Systems with Applications. - Vol. 42, iss. 24 (2015), s. 9512-9527. (http://dx.doi.org/10.1016/j.eswa.2015.07.071).
    18. J. Brzozowski, M. Szykuła, Large aperiodic semigroups, International Journal of Foundations of Computer Science. - Vol. 26, iss. 07 (2015), s. 913-931. (http://dx.doi.org/10.1142/S0129054115400067).
  • Publikacje Zakładu Złożoności Obliczeniowej i Algorytmów w roku 2014

    1. P. Gawrychowski, Ł. Jeż, A. Jeż, Validating the Knuth-Morris-Pratt failure function, fast and online, Theory of Computing Systems. - Vol. 54, iss. 2 (2014), s. 337-372. (http://dx.doi.org/10.1007/s00224-013-9522-8).
    2. A. Jeż, M. Lohrey, Approximation of smallest linear tree grammar, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) / Ernst W. Mayr, Natacha Portier (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. - (LIPIcs - Leibniz International Proceedings in Informatics ; 25). - S. 445-457. (http://dx.doi.org/10.4230/LIPIcs.STACS.2014.445).
    3. A. Jeż, The complexity of compressed membership problems for finite automata, Theory of Computing Systems. - Vol.55, iss. 4 (2014), s. 685-718. (http://dx.doi.org/10.1007/s00224-013-9443-6).
    4. A. Jeż, Context unification is in PSPACE, Automata, languages, and programming : 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings. Part II / Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias (eds.). - Berlin, Heidelberg : Springer, 2014. - (Lecture Notes in Computer Science ; 8573). - S. 244-255. (http://dx.doi.org/10.1007/978-3-662-43951-7_21).
    5. A. Jeż, V. Diekert, W. Plandowski, Finding all solutions of equations in free groups and monoids with involution, Computer science - theory and applications : 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014 : proceedings / Edward A. Hirsch, Sergei O. Kuznetsov, Jean-Eric Pin, Nikolay K. Vereshchagin (eds.). - Cham : Springer, 2014. - (Lecture Notes in Computer Science ; 8476).- S. 1-15. (http://dx.doi.org/10.1007/978-3-319-06686-8_1).
    6. A. Jeż, A really simple approximation of smallest grammar, Combinatorial Pattern Matching : 25th Annual Symposium, CPM 2014, Moscow, Russia, June 16-18, 2014. Proceedings / Alexander S. Kulikov, Sergei O. Kuznetsov, Pavel Pevzner (eds.). - Cham : Springer, 2014. - (Lecture Notes in Computer Science ; 8486).- S. 182-191. (http://dx.doi.org/10.1007/978-3-319-07566-2_19).
    7. W. Bożejko, M. Karpiński, M. Pacut, M. Wodecki, Multi-GPU parallel memetic algorithm for capacitated vehicle routing problem, Parallel Processing and Applied Mathematics : 10th International Conference, PPAM 2013, Warsaw, Poland, September 8-11, 2013, Revised Selected Papers, Part 2 / Roman Wyrzykowski, Jack Dongarra, Konrad Karczewski, Jerzy Wasniewski (eds.). - Berlin : Springer Berlin, 2014. - (Lecture Notes in Computer Science ; 8385).- S. 207-214. (http://dx.doi.org/10.1007/978-3-642-55195-6_19).
    8. J. Brzozowski, M. Szykuła, Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals, In Developments in Language Theory (DLT 2014), volume 8633 of LNCS, pages 13-24.
    9. J. Brzozowski, M. Szykuła, Large Aperiodic Semigroups, In Implementation and Application of Automata (CIAA 2014), volume 8587 of LNCS, pages 124-135, 2014.
    10. A. Jeż, A. Okhotin, Computational completeness of equations over sets of natural numbers, Information and Computation 237 (2014), 56-94. (http://www.sciencedirect.com/science/article/pii/S0890540114000637)
    11. J. Kowalski, Embedding a Card Game Language into a General Game Playing Language, Frontiers in Artificial Intelligence and Applications Volume 264: STAIRS 2014, 161 - 170. (http://ebooks.iospress.nl/volumearticle/37205).
    12. W. Bożejko, M. Karpiński, M. Pacut, M. Wodecki, Multi-GPU Parallel Memetic Algorithm for Capacitated Vehicle Routing Problem, Lecture Notes in Computer Science No. 8386, Springer (2014), 207-214.
    13. T. Jurdziński, D. Kowalski, M. Różański, G. Stachowiak, On the Impact of Geometry on Ad Hoc Communication in Wireless Networks, 33rd ACM Symposium on Principles of Distributed Computing, PODC 2014, wydane w Proceedings of the 2014 ACM symposium on Principles of distributed computing, 2014, st. 357-366. (http://dl.acm.org/citation.cfm?doid=2611462.2611487).
  • Publikacje Zakładu Złożoności Obliczeniowej i Algorytmów w roku 2012

    1. P. Gawrychowski, Tying up the loose ends in fully LZW-compressed pattern matching, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) / Christoph Dürr, Thomas Wilke (eds). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. - (LIPIcs - Leibniz International Proceedings in Informatics ; Vol. 14 ).- S. 624- 635. (http://dx.doi.org/10.4230/LIPIcs.STACS.2012.624).
    2. A. Jeż, Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P), 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) / Christoph Dürr, Thomas Wilke (eds). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. - (LIPIcs - Leibniz International Proceedings in Informatics ; Vol.14). - S. 136- 147. (http://dx.doi.org/10.4230/LIPIcs.STACS.2012.136).
    3. P. Gawrychowski, Faster algorithm for computing the edit distance between SLP-compressed strings, String Processing and Information Retrieval : 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012, Proceedings / Liliana Calderón- Benavides, Cristina González-Caro, Edgar Chávez,Nivio Ziviani (eds.). - Berlin : Springer Berlin , 2012. - (Lecture Notes in Computer Science ; 7608).- S. 229-236. (http://dx.doi.org/10.1007/978-3-642-34109-024).
    4. P. Gawrychowski, Simple and efficient LZW-compressed multiple pattern matching, Combinatorial pattern matching : 23rd annual symposium ; proceedings / CPM 2012, Helsinki, Finland, July 3 - 5, 2012 / Juha Karkkainen, Jens Stoye (eds.). - Berlin ; Heidelberg : Springer , 2012. - (Lecture Notes in Computer Science ; 7354).- S. 232-242. (http://dx.doi.org/10.1007/978-3-642-31265-619).
    5. A. Jeż, Faster fully compressed pattern matching by recompression, Automata, Languages, and Programming : 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I / ed. by Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, Roger Wattenhofer. - Berlin, Heidelberg : Springer, 2012. - (Lecture Notes in Computer Science ; 7391). - S. 533-544. (http://dx.doi.org/10.1007/978-3- 642-31594-7_45).
    6. A. Jeż, A. Okhotin, On the number of nonterminal symbols in unambiguous conjunctive grammars, Descriptional Complexity of Formal Systems : 14th International Workshop, DCFS 2012, Braga, Portugal, July 23-25, 2012 : proceedings / ed. by Martin Kutrib, Nelma Moreira, Rogério Reis. - Berlin, Heidelberg : Springer, 2012. - (Lecture Notes in Computer Science ; 7386). - S. 183-195. (http://dx.doi.org/10.1007/978-3-642-31623-4_14).
    7. A. Jeż, A. Maletti, Hyper-minimization for deterministic tree automata, Implementation and Application of Automata : 17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012 : proceedings / ed. by Nelma Moreira, Rogério Reis. - Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. - (Lecture Notes in Computer Science ; 7381). - S. 217-228. (http://dx.doi.org/10.1007/978-3-642- 31606-7_19).
    8. C. Dürr, Ł. Jeż, N. K. Thang, Online scheduling of bounded length jobs to maximize throughput, Journal of Scheduling October 2012, Volume 15, Issue 5, pp 653-664 (http://dx.doi.org/10.1007/s10951-011-0233-1).
    9. Ł. Jeż, F. Li, J. Sethuraman, C. Stein, Online scheduling of packets with agreeable deadlines, Journal ACM Transactions on Algorithms (TALG) Volume 9 Issue 1, December 2012 Article No. 5, ACM New York, NY, USA (http://doi.acm.org/10.1145/2390176.2390181).
    10. L. Epstein, Ł. Jeż, J. Sgall, R. van Stee, Online Scheduling of Jobs with Fixed Start Times on Related Machines, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Lecture Notes in Computer Science Volume 7408, 2012, pp 134-145 (http://dx.doi.org/10.1007/978-3-642-32512-0_12).
    11. A. Jeż, A. Okhotin, Representing hyper-arithmetical sets by equations over sets of integers, Theory of Computing Systems. - Vol. 51, nr 2 (2012), s. 196-228. (http://dx.doi.org/10.1007/s00224-011-9352-5).
    12. A. Jeż, T. Jurdziński, Length-reducing Automata (almost) without Auxiliary Symbols, Journal of Automata, Languages and Combinatorics, Otto-von-Guericke-Universitat, 16(2-4): 141-164 (2011); RK.
    13. T. Jurdziński, D. R. Kowalski, Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks, Distributed Computing - 26th International Sympodium (DISC 2012), LNCS 7611, Springer, 2012, 106-120; RK.
    14. T. Jurdziński, D. R. Kowalski, On the Complexity of Distributed Broadcasting and MDS Construction in Radio Networks, 16th International Conference On Principles Of Distributed Systems (OPODIS 2012), LNCS 7702, Springer, 2012, 209-224;RK.
    15. K. Paluch, K. Elbassioni, A. van Zuylen, Simpler approximation of the maximum asymmetric traveling salesman problem, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) / Christoph Dürr, Thomas Wilke (eds). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. - (LIPIcs - Leibniz International Proceedings in Informatics ; 14).- S. 501-506. (http://dx.doi.org/10.4230/LIPIcs.STACS.2012.501).
    16. K. Paluch, Faster and simpler approximation of stable matchings, Approximation and online algorithms : 9th international workshop ; revised selected papers : WAOA 2011, Saarbruecken, Germany, September 8-9, 2011 / (ed.)Roberto Solis-Oba, Giuseppe Persiano. - Berlin ; Heidelberg : Springer, 2012. - (Lecture Notes in Computer Science ; 7164). - S. 176-187.
    17. J. Byrka, K. Buchin, M. Buchin, M. Nöllenburg, Y. Okamoto, R. I. Silveira, Drawing (complete) binary tanglegrams : hardness, approximation, fixed-parameter tractability, Algorithmica. - Vol. 62, nr 1-2 (2012), s. 309-332. (http://dx.doi.org/10.1007/s00453-010-9456-3).
    18. M. Bieńkowski, T. Jurdziński, M. Korzeniowski, D. R. Kowalski, Distributed Online and Stochastic Queuing on a Multiple Access Channel, 26 Int. Symposum on DIStributed Computing (DISC), Lecture Notes in Computer Science vol. 7611, 121-135, 2012. (http://www.ii.uni.wroc.pl/~mbi/papers/2012-disc-online-mac.pdf).
    19. M. Bieńkowski, Migrating and Replicating Data in Networks Computer Science, Research and Development, vol. 27, issue 3, 169-179, 2012. Wyd.: Springer. (http://www.ii.uni.wroc.pl/~mbi/papers/2012-csrd-migration-replication-survey.pdf).
    20. M. Bieńkowski, J. Kutyłowski, The k-Resource Problem in Uniform Metric, Spaces, Theoretical Computer Science, vol. 459,42-54,2012. Wyd.: Elsevier. (http://www.sciencedirect.com/science/article/pii/S0304397512006214).
  • Publikacje Zakładu Złożoności Obliczeniowej i Algorytmów w roku 2013

    1. M. Bieńkowski, M. Chrobak, C. Dürr, M. Hurand, Ł. Jeż, A. Jeż, G. Stachowiak, Collecting Weighted Items from a Dynamic Queue, Algorithmica, January 2013, Volume 65, Issue 1, pp 60-94. (http://dx.doi.org/10.1007/s00453-011-9574-6).
    2. M. Bieńkowski, M. Chrobak, C. Dürr, M. Hurand, Ł. Jeż, G. Stachowiak, A phi-competitive algorithm for collecting items with increasing weights from a dynamic queue, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 92-102. (http://dx.doi.org/10.1016/j.tcs.2012.12.046).
    3. P. Gawrychowski, Alphabetic minimax trees in linear time, Computer Science - Theory and Applications : 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013, Proceedings / Andrei A. Bulatov, Arseny M. Shur (eds.). - Berlin : Springer, 2013. - (Lecture Notes in Computer Science ; 7913). - S. 36-48. (http://dx.doi.org/10.1007/978-3-642-38536-0_4).
    4. A. Jeż, Approximation of grammar-based compression via recompression, Combinatorial pattern matching : 24th annual symposium, CPM 2013, Bad Herrenalb, Germany, June 17 - 19, 2013 / Johannes Fischer, Peter Sanders (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture Notes in Computer Science ; Vol.7922). - S. 165-176. (http://dx.doi.org/10.1007/978-3-642-38905-4).
    5. A. Jeż, One-variable word equations in linear time, Automata, languages, and programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, Part II / Fedor V. Fomin, Rusinš Freivalds, Marta Kwiatkowska, David Peleg (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture Notes in Computer Science ; Vol.7966). - S. 324-335. (http://dx.doi.org/10.1007/978-3-642-39212-2_30).
    6. A. Jeż, Recompression: a simple and powerful technique for word equations, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) / Natacha Portier, Thomas Wilke (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. - (LIPIcs - Leibniz International Proceedings in Informatics ; Vol.20). - S. 233-244. (http://dx.doi.org/10.4230/LIPIcs.STACS.2013.233)
    7. A. Jeż, Recompression: word equations and beyond, Developments in language theory : 17th international conference ; proceedings, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013 / Marie-Pierre Béal ; Oliver Carton (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture Notes in Computer Science ; Vol.7907). - S. 12-26. (http://dx.doi.org/10.1007/978-3-642-38771- 5_2).
    8. T. Jurdziński, D. R. Kowalski, G. Stachowiak, Distributed deterministic broadcasting in wireless networks of weak devices, Automata, languages, and programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, Part II / Fedor V. Fomin, Rusinš Freivalds, Marta Kwiatkowska, David Peleg (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture Notes in Computer Science ; Vol.7966). - S. 632-644. (http://dx.doi.org/10.1007/978-3- 642-39212-2_55).
    9. A. Kisielewicz, J. Kowalski, M. Szykuła, A fast algorithm finding the shortest reset words, 19th international conference ; proceedings / COCOON 2013, Hangzhou, China, June 21 - 23, 2013 / Ding-Zhu Du ; Guochuan Zhang (ed.). - Berlin ; Heidelberg : Springer, 2013. - (Lecture notes in computer science ; Vol.7936). - S. 182-196. (http://dx.doi.org/10.1007/978-3-642-38768-5_18).
    10. A. Kisielewicz, M. Szykuła, Generating small automata and the Černý conjecture, Implementation and Application of Automata : 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings / Stavros Konstantinidis (ed.). - Berlin, Heidelberg : Springer , 2013. - (Lecture Notes in Computer Science ; Vol.7982).- S. 340-348. (http://dx.doi.org/10.1007/978-3-642-39274-0_30).
    11. J. Kowalski, M. Szykuła, Game description language compiler construction, AI 2013: Advances in Artificial Intelligence : 26th Australian Joint Conference, Dunedin, New Zealand, December 1-6, 2013. Proceedings. - Cham : Springer International Publishing, 2013. - (Lecture Notes in Computer Science ; Vol.8272). - S. 234-245. (http://dx.doi.org/10.1007/978-3-319-03680-9_26).
    12. A. Jeż, A. Maletti, Hyper-minimization for deterministic tree automata, International Journal of Foundations of Computer Science. - Vol. 24, iss. 06 (2013), s. 815-830. (http://dx.doi.org/10.1142/S0129054113400200).
    13. T. Jurdziński, G. Stachowiak, Distributed Deterministic Broadcasting in Uniform-Power Ad Hoc Wireless Networks, Fundamentals of Computation Theory - 19th International Symposium (FCT 2013) : Springer, 2013. - (Lecture Notes in Computer Science ; Vol.8070). - s. 195-209. (http://dx.doi.org/10.1007/978-3-642-40164-0_20).
    14. T. Jurdziński, D. R. Kowalski, M. Różański, G. Stachowiak, Distributed Randomized Broadcasting in Wireless Networks under the SINR Model. Distributed Computing, 27th International Symposium (DISC 2013), : Springer 2013. - (Lecture Notes in Computer Science Volume 8205). s. 373-387. (http://dx.doi.org/10.1007/978-3-642-41527-2_26).
    15. P. Gawrychowski, D. Straszak, Beating O(nm) in Approximate LZW-Compressed Pattern Matching, 24th International Symposium, ISAAC 2013, Algorithms and Computation - Springer 2013 (Lecture Notes in Computer Science Vol. 8283, s. 78-88. (http://dx.doi.org/10.1007/978-3-642-45030-3_8).
    16. P. Gawrychowski, Optimal pattern matching in LZW compressed strings, ACM Transactions on Algorithms. - Vol. 9, iss.3 (2013), nr art. 25 (17 str.). (http://dx.doi.org/10.1145/2483699.2483705).
    17. A. Jeż, A. Okhotin, Unambiguous conjunctive grammars over a one-letter alphabet, Developments in Language Theory : 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings / Marie-Pierre Béal, Olivier Carton (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture notes in computer science ; 7907). - S. 277-288. ( http://www.dx.doi.org/10.1007/978-3-642-38771-5_25).