Wojciech Czerwinski

According to our database, Wojciech Czerwinski authored at least 54 papers between 2009 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Language Equivalence is Undecidable in VASS with Restricted Nondeterminism.

Wojciech Czerwinski, Lukasz Orlikowski

CoRR, October, 2025

Reachability in One-Dimensional Pushdown Vector Addition Systems Is Decidable.

Clotilde Bizière, Wojciech Czerwinski

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Reachability and Related Problems in Vector Addition Systems with Nested Zero Tests.

Roland Guttenberg, Wojciech Czerwinski, Slawomir Lasota

Proceedings of the 40th Annual ACM/IEEE Symposium on Logic in Computer Science, 2025

Reachability in 3-VASS Is Elementary.

Wojciech Czerwinski, Ismaël Jecker, Slawomir Lasota, Lukasz Orlikowski

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Languages of Boundedly-Ambiguous Vector Addition Systems with States.

Wojciech Czerwinski, Lukasz Orlikowski

Proceedings of the 36th International Conference on Concurrency Theory, 2025

2024

Challenges of the Reachability Problem in Infinite-State Systems (Invited Paper).

Wojciech Czerwinski

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

The Tractability Border of Reachability in Simple Vector Addition Systems with States.

Dmitry Chistikov, Wojciech Czerwinski, Filip Mazowiecki, Lukasz Orlikowski, Henry Sinclair-Banks, Karol Wegrzycki

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

New Lower Bounds for Reachability in Vector Addition Systems.

Wojciech Czerwinski, Ismaël Jecker, Slawomir Lasota, Jérôme Leroux, Lukasz Orlikowski

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Languages Given by Finite Automata over the Unary Alphabet.

Wojciech Czerwinski, Maciej Debski, Tomasz Gogasz, Gordon Hoi, Sanjay Jain, Michal Skrzypczak, Frank Stephan, Christopher Tan

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Acyclic Petri and Workflow Nets with Resets.

Dmitry Chistikov, Wojciech Czerwinski, Piotr Hofman, Filip Mazowiecki, Henry Sinclair-Banks

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

2022

Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes.

Wojciech Czerwinski, Lukasz Orlikowski

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

The boundedness and zero isolation problems for weighted automata over nonnegative rationals.

Wojciech Czerwinski, Engel Lefaucheux, Filip Mazowiecki, David Purser, Markus A. Whiteland

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Language Inclusion for Boundedly-Ambiguous Vector Addition Systems Is Decidable.

Wojciech Czerwinski, Piotr Hofman

Proceedings of the 33rd International Conference on Concurrency Theory, 2022

Involved VASS Zoo (Invited Talk).

Wojciech Czerwinski

Proceedings of the 33rd International Conference on Concurrency Theory, 2022

2021

Long Runs Imply Big Separators in Vector Addition Systems.

Wojciech Czerwinski, Adam Jedrych

CoRR, 2021

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles.

Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, Anna Zych-Pawlewicz

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

New Techniques for Universality in Unambiguous Register Automata.

Wojciech Czerwinski, Antoine Mottet, Karin Quaas

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Improved Lower Bounds for Reachability in Vector Addition Systems.

Wojciech Czerwinski, Slawomir Lasota, Lukasz Orlikowski

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Reachability in Vector Addition Systems is Ackermann-complete.

Wojciech Czerwinski, Lukasz Orlikowski

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

On Dynamic Parameterized k-Path.

Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Michal Pilipczuk, Marcin Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, Anna Zych-Pawlewicz

CoRR, 2020

An Approach to Regular Separability in Vector Addition Systems.

Wojciech Czerwinski, Georg Zetzsche

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

Universality Problem for Unambiguous VASS.

Wojciech Czerwinski, Diego Figueira, Piotr Hofman

Proceedings of the 31st International Conference on Concurrency Theory, 2020

Reachability in Fixed Dimension Vector Addition Systems with States.

Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jérôme Leroux, Filip Mazowiecki

Proceedings of the 31st International Conference on Concurrency Theory, 2020

2019

The reachability problem for Petri nets is not elementary.

Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jérôme Leroux, Filip Mazowiecki

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games.

Wojciech Czerwinski, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdzinski, Ranko Lazic, Pawel Parys

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

New Pumping Technique for 2-Dimensional VASS.

Wojciech Czerwinski, Slawomir Lasota, Christof Löding, Radoslaw Piórkowski

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Improved Bounds for the Excluded-Minor Approximation of Treedepth.

Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Minimization of Tree Patterns.

Wojciech Czerwinski, Wim Martens, Matthias Niewerth, Pawel Parys

J. ACM, 2018

The Reachability Problem for Petri Nets is Not Elementary (Extended Abstract).

Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jérôme Leroux, Filip Mazowiecki

CoRR, 2018

Unboundedness Problems for Languages of Vector Addition Systems.

Wojciech Czerwinski, Piotr Hofman, Georg Zetzsche

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Regular Separability of Well-Structured Transition Systems.

Wojciech Czerwinski, Slawomir Lasota, Roland Meyer, Sebastian Muskalla, K. Narayan Kumar, Prakash Saivasan

Proceedings of the 29th International Conference on Concurrency Theory, 2018

2017

Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data.

Wojciech Czerwinski, Wim Martens, Matthias Niewerth, Pawel Parys

SIGMOD Rec., 2017

A Characterization for Decidable Separability by Piecewise Testable Languages.

Wojciech Czerwinski, Wim Martens, Lorijn van Rooijen, Marc Zeitoun, Georg Zetzsche

Discret. Math. Theor. Comput. Sci., 2017

Regular Separability of Well Structured Transition Systems.

Wojciech Czerwinski, Slawomir Lasota

CoRR, 2017

Separability of Reachability Sets of Vector Addition Systems.

Lorenzo Clemente, Wojciech Czerwinski, Slawomir Lasota, Charles Paperman

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Regular separability of one counter automata.

Wojciech Czerwinski, Slawomir Lasota

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Regular Separability of Parikh Automata.

Lorenzo Clemente, Wojciech Czerwinski, Slawomir Lasota, Charles Paperman

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Minimization of Tree Pattern Queries.

Wojciech Czerwinski, Wim Martens, Matthias Niewerth, Pawel Parys

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Reasoning About Integrity Constraints for Tree-Structured Data.

Wojciech Czerwinski, Claire David, Filip Murlak, Pawel Parys

Proceedings of the 19th International Conference on Database Theory, 2016

Shortest Paths in One-Counter Systems.

Dmitry Chistikov, Wojciech Czerwinski, Piotr Hofman, Michal Pilipczuk, Michael Wehar

Proceedings of the Foundations of Software Science and Computation Structures, 2016

2015

Non-dominating Sequences of Vectors Using only Resets and Increments.

Wojciech Czerwinski, Tomasz Gogacz, Eryk Kopczynski

Fundam. Informaticae, 2015

The (Almost) Complete Guide to Tree Pattern Containment.

Wojciech Czerwinski, Wim Martens, Pawel Parys, Marcin Przybylko

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Branching Bisimilarity of Normed BPA Processes Is in NEXPTIME.

Wojciech Czerwinski, Petr Jancar

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

A Note on Decidable Separability by Piecewise Testable Languages.

Wojciech Czerwinski, Wim Martens, Lorijn van Rooijen, Marc Zeitoun

Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015

2014

A Note on Decidable Separability by Piecewise Testable Languages.

Wojciech Czerwinski, Wim Martens

CoRR, 2014

2013

Complexity of Checking Bisimilarity between Sequential and Parallel Processes.

Wojciech Czerwinski, Petr Jancar, Martin Kot, Zdenek Sawa

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Efficient Separability of Regular Languages by Subsequences and Suffixes.

Wojciech Czerwinski, Wim Martens, Tomás Masopust

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Deciding Definability by Deterministic Regular Expressions.

Wojciech Czerwinski, Claire David, Katja Losemann, Wim Martens

Proceedings of the Foundations of Software Science and Computation Structures, 2013

2012

Partially-commutative context-free languages

Wojciech Czerwinski, Slawomir Lasota

Proceedings of the Proceedings Combined 19th International Workshop on Expressiveness in Concurrency and 9th Workshop on Structured Operational Semantics, 2012

Reachability Problem for Weak Multi-Pushdown Automata.

Wojciech Czerwinski, Piotr Hofman, Slawomir Lasota

Proceedings of the CONCUR 2012 - Concurrency Theory - 23rd International Conference, 2012

2011

Partially-commutative context-free processes: Expressibility and tractability.

Wojciech Czerwinski, Sibylle B. Fröschle, Slawomir Lasota

Inf. Comput., 2011

Decidability of Branching Bisimulation on Normed Commutative Context-Free Processes.

Wojciech Czerwinski, Piotr Hofman, Slawomir Lasota

Proceedings of the CONCUR 2011 - Concurrency Theory - 22nd International Conference, 2011

2010

Fast equivalence-checking for normed context-free processes.

Wojciech Czerwinski, Slawomir Lasota

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009

Partially-Commutative Context-Free Processes.

Wojciech Czerwinski, Sibylle B. Fröschle, Slawomir Lasota

Proceedings of the CONCUR 2009 - Concurrency Theory, 20th International Conference, 2009