Wojciech Czerwinski

According to our database, Wojciech Czerwinski authored at least 49 papers between 2009 and 2024.

Collaborative distances:

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

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

Improved Bounds for the Excluded-Minor Approximation of Treedepth.

Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk

SIAM J. Discret. Math., 2021

The Reachability Problem for Petri Nets Is Not Elementary.

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

J. ACM, 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

Regular Separability of One Counter Automata.

Wojciech Czerwinski, Slawomir Lasota

Log. Methods Comput. Sci., 2019

Shortest paths in one-counter systems.

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

Log. Methods Comput. Sci., 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

2018

Reasoning about integrity constraints for tree-structured data.

Wojciech Czerwinski, Claire David, Filip Murlak, Pawel Parys

Theory Comput. Syst., 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

Deciding definability by deterministic regular expressions.

Wojciech Czerwinski, Claire David, Katja Losemann, Wim Martens

J. Comput. Syst. Sci., 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 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

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

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

Wojciech Czerwinski, Piotr Hofman, Slawomir Lasota

Theory Comput. Syst., 2014

A Note on Decidable Separability by Piecewise Testable Languages.

Wojciech Czerwinski, Wim Martens

CoRR, 2014

2013

Reachability Problem for Weak Multi-Pushdown Automata.

Wojciech Czerwinski, Piotr Hofman, Slawomir Lasota

Log. Methods Comput. Sci., 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

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

2011

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

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

Inf. Comput., 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