Publications

Conference: International Colloquium on Automata Languages and Programming

Number of publications: 57

2025

• Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna , Stanislav Živný, Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings, 52nd EATCS International Colloquium on Automata, Languages, and Programming, Aarhus, Denmark, 8 July 2025 - 11 July 2025. See in PBN
• Kacper Kluk , Marcin Pilipczuk , Michał Pilipczuk , Giannos Stamoulis, Faster Diameter Computation in Graphs of Bounded Euler Genus, 52nd EATCS International Colloquium on Automata, Languages, and Programming, Aarhus, Denmark, 8 July 2025 - 11 July 2025. See in PBN
• Slobodan Mitrović, Anish Mukherjee, Piotr Sankowski , Wen-Horng Sheu, Faster Semi-Streaming Matchings via Alternating Trees, 52nd EATCS International Colloquium on Automata, Languages, and Programming, Aarhus, Denmark, 8 July 2025 - 11 July 2025, 334 (119) 2025, p. 1-19. See in PBN
• Gramoz Goranci, Adam Karczmarz , Ali Momeni, Nikos Parotsidis, Fully Dynamic Algorithms for Transitive Reduction, 52nd EATCS International Colloquium on Automata, Languages, and Programming, Aarhus, Denmark, 8 July 2025 - 11 July 2025, 334 (92) 2025, p. 1-20. See in PBN
• Adam Górkiewicz, Adam Karczmarz , On Incremental Approximate Shortest Paths in Directed Graphs, 52nd EATCS International Colloquium on Automata, Languages, and Programming, Aarhus, Denmark, 8 July 2025 - 11 July 2025, 334 (93) 2025, p. 1-20. See in PBN
• Wojciech Czerwiński , Ismaël Jecker , Sławomir Lasota , Łukasz Orlikowski , Reachability in 3-VASS Is Elementary, 52nd EATCS International Colloquium on Automata, Languages, and Programming, Aarhus, Denmark, 8 July 2025 - 11 July 2025, 334 (153) 2025, p. 1-20. See in PBN
• Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis, Colin Geniet , Nikolas Mählmann, Michał Pilipczuk , Wojciech Przybyszewski , Szymon Toruńczyk , Separability Properties of Monadically Dependent Graph Classes, 52nd EATCS International Colloquium on Automata, Languages, and Programming, Aarhus, Denmark, 8 July 2025 - 11 July 2025, 334 (147) 2025, p. 1-19. See in PBN

2024

• Rajesh Jayaram, Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, Piotr Sankowski , Dynamic PageRank: Algorithms and Lower Bounds, 51st International Colloquium on Automata, Languages and Programming, Tallinn, Estonia, 8 July 2024 - 12 July 2024. See in PBN
• Adam Karczmarz , Marcin Smulewicz, Fully Dynamic Strongly Connected Components in Planar Digraphs, 51st International Colloquium on Automata, Languages and Programming, Tallinn, Estonia, 8 July 2024 - 12 July 2024. See in PBN
• Mikołaj Bojańczyk , Lê Thành Dũng (Tito) Nguyen, Rafał Stefański , Function Spaces for Orbit-Finite Sets, 51st International Colloquium on Automata, Languages and Programming, Tallinn, Estonia, 8 July 2024 - 12 July 2024. See in PBN
• Paweł Rzążewski , Baris Can Esmer, Jacob Focke, Dániel Marx, Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness, 51st International Colloquium on Automata, Languages, and Programming, Tallinn, Estonia, 7 July 2024 - 11 July 2024. See in PBN
• Jakub Gajarský , Rose McCarty, On Classes of Bounded Tree Rank, Their Interpretations, and Efficient Sparsification, 51st International Colloquium on Automata, Languages and Programming, Tallinn, Estonia, 8 July 2024 - 12 July 2024. See in PBN
• Paweł Rzążewski , Marta Piecyk, Carla Groenland, Isja Mannens, Jesper Nederlof, Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters, 51st International Colloquium on Automata, Languages, and Programming, Tallinn, Estonia, 7 July 2024 - 11 July 2024. See in PBN

2023

• Mikołaj Bojańczyk , Lê Thành Dũng Nguyễn, Algebraic Recognition of Regular Functions, 50th EATCS International Colloquium on Automata, Languages and Programming, Padeborn, Germany, 10 July 2023 - 14 July 2023, 261 2023, p. 117:1-117:19. See in PBN
• Pierre Ohlmann, Michał Pilipczuk , Wojciech Przybyszewski , Szymon Toruńczyk , Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes, 50th EATCS International Colloquium on Automata, Languages and Programming, Padeborn, Germany, 10 July 2023 - 14 July 2023. See in PBN
• Marvin Künnemann, Filip Mazowiecki , Lia Schütze, Henry Sinclair-Banks, Karol Węgrzycki, Coverability in VASS Revisited: Improving Rackoff’s Bound to Obtain Conditional Optimality, 50th EATCS International Colloquium on Automata, Languages and Programming, Padeborn, Germany, 10 July 2023 - 14 July 2023. See in PBN
• Jakub Gajarský , Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk , Wojciech Przybyszewski , Sebastian Siebertz, Marek Sokołowski , Szymon Toruńczyk , Flipper Games for Monadically Stable Graph Classes, 50th EATCS International Colloquium on Automata, Languages and Programming, Padeborn, Germany, 10 July 2023 - 14 July 2023. See in PBN
• Adam Karczmarz , Piotr Sankowski , Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs, 50th EATCS International Colloquium on Automata, Languages and Programming, Padeborn, Germany, 10 July 2023 - 14 July 2023. See in PBN
• Jan Dreier, Nikolas Mahlmann, Sebastian Siebertz, Szymon Toruńczyk , Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes, 50th EATCS International Colloquium on Automata, Languages and Programming, Padeborn, Germany, 10 July 2023 - 14 July 2023, 261 2023. See in PBN
• Anders Aamand, Adam Karczmarz , Jakub Łącki, Nikos Parotsidis, Peter Rasmussen, Mikkel Thorup, Optimal Decremental Connectivity in Non-Sparse Graphs, 50th EATCS International Colloquium on Automata, Languages and Programming, Padeborn, Germany, 10 July 2023 - 14 July 2023, 261 2023, p. 6:1--6:17. See in PBN
• Hans Bodlaender, Carla Groenland, Michał Pilipczuk , Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters, 50th EATCS International Colloquium on Automata, Languages and Programming, Padeborn, Germany, 10 July 2023 - 14 July 2023. See in PBN
• Michał Włodarczyk , Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth, 50th EATCS International Colloquium on Automata, Languages and Programming, Padeborn, Germany, 10 July 2023 - 14 July 2023, 261 2023, p. 106:1-20. See in PBN

2022

• Michał Pilipczuk , Nicole Schirrmacher, Sebastian Siebertz, Szymon Toruńczyk , Alexandre Vigny, Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures, 49th International Colloquium on Automata, Languages and Programming, Paris, France, 4 July 2022 - 8 July 2022. See in PBN
• Karolina Okrasa, Paweł Rzążewski , Konrad Majewski, Tomáš Masařík, Jana Novotná, Marcin Pilipczuk, M Sokołowski, Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument, 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022), Paris, France, 3 July 2022 - 7 July 2022. See in PBN
• Jakub Gajarský , Michał Pilipczuk , Wojciech Przybyszewski , Szymon Toruńczyk , Twin-Width and Types, 49th International Colloquium on Automata, Languages and Programming, Paris, France, 4 July 2022 - 8 July 2022. See in PBN
• David Barozzini, Paweł Parys , Jan Wroblewski, Unboundedness for Recursion Schemes: A Simpler Type System, 49th International Colloquium on Automata, Languages and Programming, Paris, France, 4 July 2022 - 8 July 2022, 229 2022, p. 112:1--112:19. See in PBN

2021

• Lorenzo Clemente , Michał Skrzypczak , Deterministic and Game Separability for Regular Languages of Infinite Trees, 48th International Colloquium on Automata, Languages and Programming, Glasgow, the United Kingdom of Great Britain and Northern Ireland, 12 July 2021 - 16 July 2021, 198 2021, p. 126:1--126:15. See in PBN
• Adam Karczmarz , Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems, 48th International Colloquium on Automata, Languages and Programming, Glasgow, the United Kingdom of Great Britain and Northern Ireland, 12 July 2021 - 16 July 2021, 198 2021, p. 83:1--83:20. See in PBN
• Paweł Parys , Higher-Order Model Checking Step by Step, 48th International Colloquium on Automata, Languages and Programming, Glasgow, the United Kingdom of Great Britain and Northern Ireland, 12 July 2021 - 16 July 2021, 198 2021, p. 140:1--140:16. See in PBN
• Wojciech Czerwiński , Sławomir Lasota , Łukasz Orlikowski, Improved Lower Bounds for Reachability in Vector Addition Systems, 48th International Colloquium on Automata, Languages and Programming, Glasgow, the United Kingdom of Great Britain and Northern Ireland, 12 July 2021 - 16 July 2021. See in PBN
• Wojciech Czerwiński , Antoine Mottet, Karin Quaas, New Techniques for Universality in Unambiguous Register Automata, 48th International Colloquium on Automata, Languages and Programming, Glasgow, the United Kingdom of Great Britain and Northern Ireland, 12 July 2021 - 16 July 2021. See in PBN

2020

• Damian Niwiński , Marcin Przybyłko, Michał Skrzypczak , Computing Measures of Weak-MSO Definable Sets of Trees, 47th International Colloquium on Automata, Languages, and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020, 168 2020, p. 136:1--136:18. See in PBN
• David Barozzini, Lorenzo Clemente , Thomas Colcombet, Paweł Parys , Cost Automata, Safe Schemes, and Downward Closures, 47th International Colloquium on Automata, Languages and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020, 168 2020, p. 109:1-109:18. See in PBN
• Michaël Cadilhac, Charles Paperman, Michał Pilipczuk , Géraud Sénizergues, Filip Mazowiecki , On Polynomial Recursive Sequences, Leibniz International Proceedings in Informatics, LIPIcs, 47th International Colloquium on Automata, Languages, and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020, 168 2020, p. 117:1--117:17. See in PBN
• Michał Włodarczyk , Parameterized Inapproximability for Steiner Orientation by Gap Amplification, 47th International Colloquium on Automata, Languages and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020. See in PBN
• Mikołaj Bojańczyk , Rafał Stefański , Single-Use Automata and Transducers for Infinite Alphabets, 47th International Colloquium on Automata, Languages and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020. See in PBN
• Alex Brandts, Marcin Wrochna , Stanislav Zivny, The complexity of promise SAT on non-boolean domains, Leibniz International Proceedings in Informatics, 47th International Colloquium on Automata, Languages, and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020. See in PBN
• Lorenzo Clemente , Sławomir Lasota , Radosław Piórkowski, Timed Games and Deterministic Separability, 47th International Colloquium on Automata, Languages, and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020. See in PBN

2019

• Mikołaj Bojańczyk , Sandra Kiefer, Nathan Lhote, String-to-String Interpretations With Polynomial-Size Output, 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 8 July 2019 - 12 July 2019. See in PBN

2018

• Sławomir Lasota , Lorenzo Clemente , Binary Reachability of Timed Pushdown Automata via Quantifier Elimination and Cyclic Order Atoms, 45th International Colloquium on Automata, Languages, and Programming, Praha, Czechia, 9 July 2018 - 13 July 2018. See in PBN
• Michał Pilipczuk , Sebastian Siebertz, Stephan Kreutzer, Jaroslav Nešetřil, Patrice Ossona de Mendez, Szymon Toruńczyk , Jakub Gajarský , First-Order Interpretations of Bounded Expansion Classes, 45th International Colloquium on Automata, Languages, and Programming, Praha, Czechia, 9 July 2018 - 13 July 2018. See in PBN
• Paweł Gawrychowski, Adam Karczmarz , Improved bounds for shortest paths in dense distance graphs, 45th International Colloquium on Automata, Languages, and Programming, Praha, Czechia, 9 July 2018 - 13 July 2018. See in PBN
• Piotr Sankowski , NC Algorithms for Weighted Planar Perfect Matching and Related Problems, 45th International Colloquium on Automata, Languages, and Programming, Praha, Czechia, 9 July 2018 - 13 July 2018. See in PBN
• Jarosław Byrka, Piotr Skowron , Krzysztof Sornat, Proportional approval voting, harmonic k-median, and negative association, 45th International Colloquium on Automata, Languages, and Programming, Praha, Czechia, 9 July 2018 - 13 July 2018. See in PBN
• Michał Skrzypczak , Unambiguous Languages Exhaust the Index Hierarchy, 45th International Colloquium on Automata, Languages, and Programming, Praha, Czechia, 9 July 2018 - 13 July 2018. See in PBN
• Wojciech Czerwiński , Piotr Hofman , Georg Zetzsche, Unboundedness Problems for Languages of Vector Addition Systems, 45th International Colloquium on Automata, Languages, and Programming, Praha, Czechia, 9 July 2018 - 13 July 2018. See in PBN

2017

• Marcin Bieńkowski, Jarosław Byrka, Marcin Mucha , Dynamic beats fixed : on phase-based algorithms for file migration, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
• Hugo Gimbert, Mikołaj Bojańczyk , Edon Kelmendi, Emptiness of Zero Automata Is Decidable, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
• Florian Barbero, Christophe Paul, Michał Pilipczuk , Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
• Archontia Giannopoulou, Michał Pilipczuk , Jean-florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna , Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
• Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michał Pilipczuk , Roman Rabinovich, Sebastian Siebertz, Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
• Marek Cygan , Marcin Mucha , Karol Węgrzycki, Michał Włodarczyk , On Problems Equivalent to (min, +)-Convolution, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
• Charles Paperman, Sławomir Lasota , Wojciech Czerwiński , Lorenzo Clemente , Regular Separability of Parikh Automata, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
• Marek Adamczyk, Fabrizio Grandoni, Stefano Leonardi, Michał Włodarczyk , When the Optimum is also Blind: a New Perspective on Universal Optimization, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
• Mikołaj Bojańczyk , Laure Daviaud, Bruno Guillon, Vincent Penelle, Which Classes of Origin Graphs Are Generated by Transducers, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN

2015

• Mikołaj Bojańczyk , Filip Murlak , Adam Witkowski, Containment of Monadic Datalog Programs via Bounded Clique-Width, 42nd International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 6 July 2015 - 10 July 2015. See in PBN

2006

• Filip Murlak , The Wadge Hierarchy of Deterministic Tree Languages, Lecture Notes in Computer Science, 33rd International Colloquium on Automata, Languages and Programming, Wenecja, Italy, 10 July 2006 - 14 July 2006. See in PBN