Talks
Challenges of the Reachability Problem in Infinite-State Systems
Invited talk on MFCS 2024, slides,
paper
The Reachability Problem for Computation Models
Invited talk on Computational Logic and Applications 2023, slides
Recent Advances on the Reachability Problem for VASSes by Examples
Invited talk on Reachability Problems 2022, slides,
recording
Techniques for Unambiguous Systems
Invited talk on GandALF 2022, slides,
recording
Reachability in Vector Addition Systems by Examples
Invited talk on CONCUR 2022, paper, slides,
recording
The Reachability Problem for Vector Addition Systems
MOVEP Summer School 2022, slides
Deciding Language Equivalence for Unambiguous VASSes
Invited talk on Daghstuhl Seminar on Unambiguity 2021, slides
The Reachability Problem for Vector Addition Systems is Ackermann-complete
Bordeaux Online Seminar 2021, slides
The Reachability Problem for Vector Addition Systems is Not Elementary
Dresden Online Seminar 2020, slides
Publications
Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman, Filip Mazowiecki, Henry Sinclair-Banks
Acyclic Petri and Workflow Nets with Resets
FSTTCS 2023, available here
Wojciech Czerwiński, Maciej Dębski, Tomasz Gogasz, Gordon Hoi, Sanjay Jain, Michał Skrzypczak, Frank Stephan, Christopher Tan
Languages Given by Finite Automata over the Unary Alphabet
FSTTCS 2023, available here
Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota, Jérôme Leroux, Łukasz Orlikowski
New Lower Bounds for Reachability in Vector Addition Systems
FSTTCS 2023, available here
Wojciech Czerwiński, Piotr Hofman
Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
CONCUR 2022, Best Paper Award, available on arxiv
Wojciech Czerwiński, Engel Lefaucheux, Filip Mazowiecki, David Purser, Markus A. Whiteland
The boundedness and zero isolation problems for weighted automata over nonnegative rationals
LICS 2022, available on arxiv
Wojciech Czerwiński, Łukasz Orlikowski
Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes
LICS 2022, available on arxiv, slides,
recording (short talk on Highlights 2022)
Wojciech Czerwiński, Łukasz Orlikowski
Reachability in Vector Addition Systems is Ackermann-complete
FOCS 2021, available on arxiv,
recording (talk by Łukasz Orlikowski)
Wojciech Czerwiński, Sławomir Lasota, Łukasz Orlikowski
Improved Lower Bounds for Reachability in Vector Addition Systems
ICALP 2021, available on DROPS,
recording (talk by Sławomir Lasota)
Wojciech Czerwiński, Antoine Mottet, Karin Quaas
New Techniques for Universality in Unambiguous Register Automata
ICALP 2021, available on arxiv, slides,
recording
Jiehua Chen, Wojciech Czerwiński, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk,
Michał Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, Anna Zych-Pawlewicz
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
SODA 2021, available on SIAM
Wojciech Czerwiński, Diego Figueira, Piotr Hofman
Universality Problem for Unambiguous VASS
CONCUR 2020, available on arxiv, slides,
recording
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, Filip Mazowiecki
Reachability in Fixed Dimension Vector Addition Systems with States
CONCUR 2020, available on arxiv, slides
Wojciech Czerwiński, Georg Zetzsche
An Approach to Regular Separability in Vector Addition Systems
LICS 2020, available on arxiv,
slides, slides (short talk),
recording
Wojciech Czerwiński, Wojciech Nadara, Marcin Pilipczuk
Improved Bounds for the Excluded-Minor Approximation of Treedepth
ESA 2019, available on arxiv
Wojciech Czerwiński, Sławomir Lasota, Christof Löding, Radosław Piórkowski
New Pumping Technique for 2-Dimensional VASS
MFCS 2019, available on arxiv,
recording (talk by Radosław Piórkowski)
Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdzinski, Ranko Lazić, Paweł Parys
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
SODA 2019, available on arxiv
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, Filip Mazowiecki
The reachability problem for Petri nets is not elementary
STOC 2019, Best Paper Award, available on arxiv,
slides, slides (short talk)
Wojciech Czerwiński, Sławomir Lasota, Roland Meyer, Sebastian Muskalla, K. Narayan Kumar, Prakash Saivasan
Regular Separability of Well-Structured Transition Systems
CONCUR 2018, available on arxiv
Wojciech Czerwiński, Piotr Hofman, Georg Zetzsche
Unboundedness Problems for Languages of Vector Addition Systems
ICALP 2018, available on arxiv, slides
Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota, Charles Paperman
Regular Separability of Parikh Automata
ICALP 2017, available on arxiv
Wojciech Czerwiński, Sławomir Lasota
Regular separability of one counter automata
LICS 2017, available on arxiv,
slides, slides (short talk)
Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota, Charles Paperman
Separability of Reachability Sets of Vector Addition Systems
STACS 2017, available on arxiv, slides
Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman, Michał Pilipczuk, Michael Wehar
Shortest Paths in One-Counter Systems
FoSSaCS 2016, available on arxiv
Wojciech Czerwiński, Claire David, Filip Murlak, Paweł Parys
Reasoning About Integrity Constraints for Tree-Structured Data
ICDT 2016
Wojciech Czerwiński, Wim Martens, Matthias Niewerth, Paweł Parys
Minimization of Tree Pattern Queries
PODS 2016, JACM
Wojciech Czerwiński, Tomasz Gogacz, Eryk Kopczyński
Non-dominating Sequences of Vectors Using only Resets and Increments
Fundamenta Informaticae, available on arxiv
Wojciech Czerwiński, Wim Martens, Lorijn van Rooijen, Marc Zeitoun
A Note on Decidable Separability by Piecewise Testable Languages
FCT 2015, available on arxiv,
slides, slides (short talk, only part of the work)
Wojciech Czerwiński, Petr Jančar
Branching Bisimilarity of Normed BPA Processes Is in NEXPTIME
LICS 2015, available on arxiv, slides
Wojciech Czerwiński, Wim Martens, Paweł Parys, Marcin Przybyłko
The (Almost) Complete Guide to Tree Pattern Containment
PODS 2015, slides, slides (short talk)
Wojciech Czerwiński, Claire David, Katja Losemann, Wim Martens
Deciding Definability by Deterministic Regular Expressions
FoSSaCS 2013
Wojciech Czerwiński, Wim Martens, Tomás Masopust
Efficient Separability of Regular Languages by Subsequences and Suffixes
ICALP 2013, available on arxiv,
slides, slides (short talk),
Wojciech Czerwiński, Petr Jančar, Martin Kot, Zdeněk Sawa
Complexity of Checking Bisimilarity between Sequential and Parallel Processes
MFCS 2013
Wojciech Czerwiński, Piotr Hofman, Sławomir Lasota
Reachability Problem for Weak Multi-Pushdown Automata
CONCUR 2012, available on arxiv
Wojciech Czerwiński, Sławomir Lasota
Partially-commutative context-free languages
EXPRESS/SOS 2012, available on arxiv,
slides, slides (short talk)
Wojciech Czerwiński, Piotr Hofman, Sławomir Lasota
Decidability of Branching Bisimulation on Normed Commutative Context-Free Processes
CONCUR 2011, slides, slides (short talk)
Wojciech Czerwiński, Sławomir Lasota
Fast equivalence-checking for normed context-free processes
FSTTCS 2010, slides
Wojciech Czerwiński, Sibylle B. Fröschle, Sławomir Lasota
Partially-Commutative Context-Free Processes
CONCUR 2009, slides (short talk)
Other
PhD Thesis
Habilitation overview: short description of interesting results in my research (2013-2019)