Publications

Journal: Theoretical Computer Science

Number of publications: 79

2018

• Tomasz Kociumaka, Jakub W. Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń, On the string consensus problem and the Manhattan sequence consensus problem, Theoretical Computer Science 710 2018, p. 126–138.see in PBN
• Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń, Efficient algorithms for shortest partial seeds in words, Theoretical Computer Science 710 2018, p. 139–147.see in PBN
• Wojciech Plandowski and Aleksy Andrzej Schubert, On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note), Theoretical Computer Science 2018.see in PBN
• Damian Repke and Wojciech Rytter, On Semi-perfect de Bruijn words, Theoretical Computer Science 720 2018, p. 55–63.see in PBN
• Wojciech Plandowski, On PSPACE generation of a solution set of a word equation and its applications, Theoretical Computer Science 2018.see in PBN

2017

• Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń, Covering problems for partial words and for indeterminate strings, Theoretical Computer Science 698 2017, p. 25–39.see in PBN

2016

• Tomasz Kociumaka, Jakub Jan Radoszewski, Wojciech Rytter and Tomasz Waleń, Maximum number of distinct and nonequivalent nonstandard squares in a word, Theoretical Computer Science 648 2016, p. 84–95.see in PBN
• Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Jan Radoszewski, Wojciech Rytter and Tomasz Waleń, Order-preserving indexing, Theoretical Computer Science 638 2016, p. 122–135.see in PBN
• Gabriele Fici, Tomasz Kociumaka, Thierry Lecroq, Arnaud Lefebvre and Élise Prieur-Gaston, Fast computation of Abelian runs, Theoretical Computer Science 656, Part B 2016, p. 256–264.see in PBN
• Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka, Ignat Kolesnichenko and Tatiana Starikovskaya, Computing minimal and maximal suffixes of a substring, Theoretical Computer Science 638 2016, p. 112–121.see in PBN
• Krzysztof Ziemiański, On execution spaces of PV-programs, Theoretical Computer Science 619 (2016) 2016, p. 87–98.see in PBN
• Jakub Pawlewicz and Ryan B. Hayward, Conspiracy number search with relative sibling scores, Theoretical Computer Science 644 2016, p. 127–142.see in PBN
• Wojciech Rytter, Two fast constructions of compact representations of binary words with given set of periods, Theoretical Computer Science 656, Part B 2016, p. 180–187.see in PBN
• Aistis Atminas, Marcin Kamiński and Jean-Florent Raymond, Scattered packings of cycles, Theoretical Computer Science 647 2016, p. 33–42.see in PBN
• Sławomir Lasota and Marcin Poturalski, Undecidability of performance equivalence of Petri nets, Theoretical Computer Science 655 2016, p. 109–119.see in PBN
• Łukasz Kowalik and Juho Lauri, On finding rainbow and colorful paths, Theoretical Computer Science 628 2016, p. 110–114.see in PBN
• Marthe Bonamy and Łukasz Kowalik, A 13k-kernel for planar feedback vertex set via region decomposition, Theoretical Computer Science 645 2016, p. 25–40.see in PBN

2015

• Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń, Linear-Time Version of Holub's Algorithm for Morphic Imprimitivity Testing, Theoretical Computer Science 602 2015, p. 7–21.see in PBN
• Marcin Peczarski and Gerold Jäger, Bounding memory for mastermind might not make it harder, Theoretical Computer Science (596) 2015, p. 55–66.see in PBN
• Arseny Shur and Wojciech Rytter, Searching for Zimin patterns, Theoretical Computer Science 571 2015, p. 50–57.see in PBN
• Mirosław Kowaluk and Gabriela Majewska, New sequential and parallel algorithms for computing the β-spectrum, Theoretical Computer Science 590 2015, p. 73–85.see in PBN
• Peter Floderus, Mirosław Kowaluk, Andrzej Lingas and Eva-Marta Lundell, Induced subgraph isomorphism: Are some patterns substantially easier than others?, Theoretical Computer Science 605 2015, p. 119–128.see in PBN

2014

• Łukasz Kowalik and Marcin Ireneusz Mucha, A 9k kernel for nonseparating independent set in planar graphs, Theoretical Computer Science 2014.see in PBN
• Ken-etsu Fujita and Aleksy Andrzej Schubert, Existential type systems between Church and Curry style (type-free style), Theoretical Computer Science 549 2014, p. 17–35.see in PBN
• Tomasz Kociumaka, Jakub Pachocki, Jakub Jan Radoszewski, Wojciech Rytter and Tomasz Waleń, Efficient counting of square substrings in a tree, Theoretical Computer Science 544 2014, p. 60–73.see in PBN
• Angelo Fanelli, Dariusz Leniowski, Gianpiero Monaco and Piotr Sankowski, The ring design game with fair cost allocation, Theoretical Computer Science 2014.see in PBN
• Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Jakub Jan Radoszewski, Wojciech Rytter and Tomasz Waleń, Extracting powers and periods in a word from its runs structure, Theoretical Computer Science 521 (Complete) 2014, p. 29–41.see in PBN

2013

• Tomas Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, W. F. Smyth and Wojciech Tyczyński, Enhanced string covering, Theoretical Computer Science 506 2013, p. 102–114.see in PBN
• Michalis Christou, Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Solon P. Pissis, Jakub Jan Radoszewski, Wojciech Rytter, Bartosz Szreder and Tomasz Waleń, Efficient seed computation revisited, Theoretical Computer Science 483 (Complete) 2013, p. 171–181.see in PBN
• P.A. Golovach, Marcin Kamiński, D. Paulusma and D.M. Thilikos, Increasing the minimum degree of a graph by contractions, Theoretical Computer Science 481 (Complete) 2013, p. 74–84.see in PBN

2012

• Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, M. Sohel Rahman, German Tischler and Tomasz Waleń, Improved algorithms for the range next value problem and applications, Theoretical Computer Science 434 2012, p. 23–34.see in PBN
• Andrzej Skowron and Piotr Wasilewski, Interactive information systems: Toward perception based computing, Theoretical Computer Science 454 2012, p. 240–260.see in PBN

2011

• Bartosz Klin, Bialgebras for structural operational semantics: an introduction, Theoretical Computer Science 412 (38) 2011, p. 5043–5069.see in PBN
• Gudmund Frandsen and Piotr Sankowski, Dynamic normal forms and dynamic characteristic polynomial, Theoretical Computer Science 412 (16) 2011, p. 1470–1483.see in PBN
• Andrzej Skowron and Piotr Wasilewski, Information systems in modeling interactive computations on granules, Theoretical Computer Science 412 (42) 2011, p. 5939–5959.see in PBN
• Dominik Ślęzak and Marcin Szczuka, Feedforward neural networks for compound signals, Theoretical Computer Science 412 (42) 2011, p. 5960–5973.see in PBN
• Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk and Jakub Wojtaszczyk, Dominating set is fixed parameter tractable in claw-free graphs, Theoretical Computer Science 412 (50) 2011, p. 6982–7000.see in PBN

2010

• Marek Cygan and Marcin Pilipczuk, Exact and approximate bandwidth, Theoretical Computer Science 411 (40-42) 2010, p. 3701–3713.see in PBN

2009

• Piotr Sankowski, Maximum weight bipartite matching in matrix multiplication time, Theoretical Computer Science 410 (44) 2009, p. 4480–4488.see in PBN
• Maxime Crochemore, Lucian Ilie and Wojciech Rytter, Repetitions in strings: Algorithms and combinatorics, Theoretical Computer Science 410 (50) 2009, p. 5227–5235.see in PBN
• Lars Arge, Christian Cachin and Andrzej Tarlecki, Preface, Theoretical Computer Science 410 (18) 2009.see in PBN
• Łukasz Kowalik, Improved edge-coloring with three colors, Theoretical Computer Science 410 (38-40) 2009, p. 3733–3742.see in PBN
• Marek Biskup and Wojciech Plandowski, Shortest synchronizing strings for Huffman codes, Theoretical Computer Science 410 (38-40) 2009, p. 3925–3941.see in PBN
• Elena Czeizler and Wojciech Plandowski, On systems of word equations over three unknowns with at most six occurrences of one of the unknowns, Theoretical Computer Science 410 (30-32) 2009, p. 2889–2909.see in PBN
• Paweł Baturo and Wojciech Rytter, Compressed string-matching in standard Sturmian words, Theoretical Computer Science 410 (30-32) 2009, p. 2804–2810.see in PBN
• Łukasz Kowalik and Marcin Mucha, Deterministic 7/8-approximation for the Metric Maximum TSP, Theoretical Computer Science 410 2009, p. 5000–5009.see in PBN

2008

• Dariusz R. Kowalski and Adam Malinowski, How to meet in anonymous network, Theoretical Computer Science 399 (1-2) 2008, p. 141–156.see in PBN

2007

• Cedric Bastien, Jurek Czyzowicz, Wojciech Fraczak and Wojciech Rytter, Equivalence of simple functions, Theoretical Computer Science 376 (1) 2007, p. 42–51.see in PBN
• Sibylle Froeschle and Sławomir Lasota, Causality Versus True-Concurrency, Theoretical Computer Science 386 2007, p. 169–187.see in PBN
• Artur Czumaj, Mirosław Kowaluk and Andrzej Lingas, Faster algorithms for finding lowest common ancestors in directed acyclic graphs, Theoretical Computer Science 380 (1) 2007, p. 37–46.see in PBN

2006

• Mikołaj Bojańczyk and Thomas Colcombet, Tree-walking automata cannot be determinized, Theoretical Computer Science 350 (3) 2006, p. 164–173.see in PBN
• Sławomir Lasota, Decidability of Performance Equivalence for Basic Parallel Processes, Theoretical Computer Science 360 (1-3) 2006, p. 172–192.see in PBN
• Anh Linh Nguyen, Multimodal Logic Programming, Theoretical Computer Science 360 2006, p. 247–288.see in PBN
• Paweł Górecki and Jerzy Tiuryn, DLS-trees: a model of evolutionary scenarios, Theoretical Computer Science 359 (1-3) 2006, p. 378–399.see in PBN
• Wojciech Rytter, The structure of subword graphs and suffix trees of Fibonacci words, Theoretical Computer Science 363 2006, p. 211–223.see in PBN
• Cedric Bastien, Jurek Czyzowicz, Wojciech Fraczak and Wojciech Rytter, Prime normal form and equivalence of simple grammars, Theoretical Computer Science 363 (2) 2006, p. 124–134.see in PBN
• Thomas Colcombet and Damian Niwiński, On the positional determinacy of edge-labeled games, Theoretical Computer Science 352 (3) 2006, p. 190–196.see in PBN

2005

• Lutz Schröder, Till Mossakowski, Andrzej Tarlecki, Bartek Klin and Piotr Hoffman, Amalgamation in the semantics of CASL, Theoretical Computer Science 331 2005, p. 215–247.see in PBN
• Lutz Schroeder, Till Mossakowski, Andrzej Tarlecki, Piotr Hoffman and Bartosz Klin, Amalgamation in the semantics of CASL, Theoretical Computer Science 331 (1) 2005, p. 215–247.see in PBN
• Juhani Karhumäki, Wojciech Plandowski and Wojciech Rytter, On the complexity of decidable cases of the commutation problem of languages, Theoretical Computer Science 337 (1-3) 2005, p. 105–118.see in PBN

2004

• Zofia Adamowicz and Leszek Aleksander Kołodziejczyk, Well-behaved principles alternative to bounded induction, Theoretical Computer Science 322 2004, p. 5–16.see in PBN

2003

• Mikołaj Bojańczyk, The Finite Graph Problem for Two-Way Alternating Automata, Theoretical Computer Science 298 (3) 2003, p. 511–528.see in PBN
• Artur Czumaj, Leszek Gasieniec, Daya Gaur, Ramesh Krishnamurti, Wojciech Rytter and Michele Zito, On polynomial-time approximation algorithms for the variable length scheduling problem, Theoretical Computer Science 302 2003, p. 489–495.see in PBN
• Juhani Karhumaeki, Jan Manuch and Wojciech Plandowski, A defect theorem for bi-infinite words, Theoretical Computer Science 292 (1) 2003, p. 237–243.see in PBN
• Damian Niwiński and Igor Walukiewicz, A gap property of deterministic tree languages, Theoretical Computer Science 303 2003, p. 215–231.see in PBN
• Wojciech Rytter, Application of Lempel-Ziv factorization to the approximation of grammar-based compression, Theoretical Computer Science 299 (1-3) 2003, p. 763–774.see in PBN
• Wojciech Rytter, On maximal suffices and constant space versions of KMP algorithm, Theoretical Computer Science 302 2003, p. 211–222.see in PBN

2002

• Andrzej Tarlecki, E. Astesiano, M. Bidoit, H. Kirchner, B. Krieg-Brueckner, P. Mosses and D. Sannella, CASL: The Common Algebraic Specification Language, Theoretical Computer Science 286 (2) 2002, p. 153–196.see in PBN
• Krzysztof Diks, E. Kranakis, D. Krizanc and A. Pelc, The impact of information on broadcasting time in linear radio networks, Theoretical Computer Science 287 (2) 2002, p. 449–471.see in PBN
• Sławomir Lasota, Coalgebra morphisms subsume open maps, Theoretical Computer Science 280 2002, p. 123–135.see in PBN
• Egidio Astesiano, Michel Bidoit, Hélène Kirchner, Bernd Krieg-Brückner, Peter D. Mosses, Donald Sannella and Andrzej Tarlecki, CASL: the Common Algebraic Specification Language, Theoretical Computer Science 286 2002, p. 153–196.see in PBN

2001

• A. Czumaj, I. Finch, L. Gąsieniec, A. Gibbons, P. Leng, Wojciech Rytter and M. Zito, Efficient web searching using temporal factors, Theoretical Computer Science 262 (1) 2001, p. 569–582.see in PBN
• Henryk Woźniakowski and David Lee, Approximate evaluations of characteristic polynomials of Boolean functions., Theoretical Computer Science 262 (1-2) 2001, p. 37–68.see in PBN

2000

• Bogdan Chlebus, A. Czumaj, Leszek Gąsieniec, Mirosław Kowaluk and Wojciech Plandowski, Algorithms for the parallel alternating direction access machine, Theoretical Computer Science 245 (2) 2000, p. 151–173.see in PBN

1997

• Stefan Kahrs, Donald Sannella and Andrzej Tarlecki, The definition of Extended ML: A gentle introduction, Theoretical Computer Science 173 1997, p. 445–484.see in PBN

1991

• Andrzej Szałas, On Strictly Arithmetical Completeness in Logics of Programs, Theoretical Computer Science 79 (2) 1991, p. 341–355.see in PBN

1988

• Leszek Holenderski and Andrzej Szałas, Incompleteness of First-Order Temporal Logic with Until, Theoretical Computer Science 57 1988, p. 317–325.see in PBN

1987

• Andrzej Szałas, A Complete Axiomatic Characterization of First-Order Temporal Logic of Linear Time, Theoretical Computer Science 54 1987, p. 199–214.see in PBN

1986

• Andrzej Szałas, Concerning the Semantic Consequence Relation in First-Order Temporal Logic, Theoretical Computer Science 47 (3) 1986, p. 329–334.see in PBN