Pawel Parys

According to our database, Pawel Parys authored at least 57 papers between 2006 and 2024.

Collaborative distances:

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

2024

Extending the WMSO+U Logic with Quantification over Tuples.

Anita Badyl, Pawel Parys

Proceedings of the 32nd EACSL Annual Conference on Computer Science Logic, 2024

2023

The Probabilistic Rabin Tree Theorem.

Damian Niwinski, Pawel Parys, Michal Skrzypczak

CoRR, 2023

Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete.

Stefan Göller, Pawel Parys

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

The Probabilistic Rabin Tree Theorem^*.

Damian Niwinski, Pawel Parys, Michal Skrzypczak

Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science, 2023

Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games.

Pawel Parys, Aleksander Wiacek

Proceedings of the Unity of Logic and Computation, 2023

2022

A Recursive Approach to Solving Parity Games in Quasipolynomial Time.

Karoliina Lehtinen, Pawel Parys, Sven Schewe, Dominik Wojtczak

Log. Methods Comput. Sci., 2022

The Caucal hierarchy: Interpretations in the (W)MSO+U logic.

Pawel Parys

Inf. Comput., 2022

Cost Automata, Safe Schemes, and Downward Closures.

David Barozzini, Lorenzo Clemente, Thomas Colcombet, Pawel Parys

Fundam. Informaticae, 2022

Unboundedness for Recursion Schemes: A Simpler Type System.

David Barozzini, Pawel Parys, Jan Wroblewski

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Higher-Order Model Checking Step by Step.

Pawel Parys

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

Shelah-Stupp's and Muchnik's Iterations Revisited.

Pawel Parys

Proceedings of the Computer Science - Theory and Applications, 2021

A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation.

André Arnold, Damian Niwinski, Pawel Parys

Proceedings of the 29th EACSL Annual Conference on Computer Science Logic, 2021

2020

On the Expressive Power of Higher-Order Pushdown Systems.

Pawel Parys

Log. Methods Comput. Sci., 2020

Recursion Schemes, the MSO Logic, and the U quantifier.

Pawel Parys

Log. Methods Comput. Sci., 2020

A Type System Describing Unboundedness.

Pawel Parys

Discret. Math. Theor. Comput. Sci., 2020

Compositionality of the MSO+U Logic.

Pawel Parys

CoRR, 2020

Bisimulation Finiteness of Pushdown Systems Is Elementary.

Stefan Göller, Pawel Parys

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

Higher-Order Nonemptiness Step by Step.

Pawel Parys

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Parity Games: Another View on Lehtinen's Algorithm.

Pawel Parys

Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

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

Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time.

Pawel Parys

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

Extensions of the Caucal Hierarchy?

Pawel Parys

Proceedings of the Language and Automata Theory and Applications, 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

Intersection Types for Unboundedness Problems.

Pawel Parys

Proceedings of the Proceedings Twelfth Workshop on Developments in Computational Models and Ninth Workshop on Intersection Types and Related Systems, 2018

Recursion Schemes and the WMSO+U Logic.

Pawel Parys

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Homogeneity Without Loss of Generality.

Pawel Parys

Proceedings of the 3rd International Conference on Formal Structures for Computation and Deduction, 2018

2017

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

Wojciech Czerwinski, Wim Martens, Matthias Niewerth, Pawel Parys

SIGMOD Rec., 2017

The Complexity of the Diagonal Problem for Recursion Schemes.

Pawel Parys

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

A characterization of lambda-terms transforming numerals.

Pawel Parys

J. Funct. Program., 2016

Weak containment for partial words is coNP-complete.

Pawel Parys

Inf. Process. Lett., 2016

Intersection Types and Counting.

Pawel Parys

Proceedings of the Proceedings Eighth Workshop on Intersection Types and Related Systems, 2016

The MSO+U Theory of (N, <) Is Undecidable.

Mikolaj Bojanczyk, Pawel Parys, Szymon Torunczyk

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

On a Fragment of AMSO and Tiling Systems.

Achim Blumensath, Thomas Colcombet, Pawel Parys

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 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

The Diagonal Problem for Higher-Order Recursion Schemes is Decidable.

Lorenzo Clemente, Pawel Parys, Sylvain Salvati, Igor Walukiewicz

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

Models of Lambda-Calculus and the Weak MSO Logic.

Pawel Parys, Szymon Torunczyk

Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

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

Ordered Tree-Pushdown Systems.

Lorenzo Clemente, Pawel Parys, Sylvain Salvati, Igor Walukiewicz

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

How Many Numbers Can a Lambda-Term Contain?

Pawel Parys

Proceedings of the Functional and Logic Programming - 12th International Symposium, 2014

First-Order Logic on CPDA Graphs.

Pawel Parys

Proceedings of the Computer Science - Theory and Applications, 2014

Two-way cost automata and cost logics over infinite trees.

Achim Blumensath, Thomas Colcombet, Denis Kuperberg, Pawel Parys, Michael Vanden Boom

Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014

2013

Some results on complexity of µ-calculus evaluation in the black-box model.

Pawel Parys

RAIRO Theor. Informatics Appl., 2013

2012

Higher-Order Pushdown Systems with Data

Pawel Parys

Proceedings of the Proceedings Third International Symposium on Games, 2012

Weak Alternating Timed Automata

Pawel Parys, Igor Walukiewicz

Log. Methods Comput. Sci., 2012

A Pumping Lemma for Pushdown Graphs of Any Level.

Pawel Parys

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Strictness of the Collapsible Pushdown Hierarchy.

Alexander Kartzow, Pawel Parys

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

On the Significance of the Collapse Operation.

Pawel Parys

Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

Decidable classes of documents for XPath.

Vince Bárány, Mikolaj Bojanczyk, Diego Figueira, Pawel Parys

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

Variants of Collapsible Pushdown Systems.

Pawel Parys

Proceedings of the Computer Science Logic (CSL'12), 2012

2011

XPath evaluation in linear time.

Mikolaj Bojanczyk, Pawel Parys

J. ACM, 2011

Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata.

Pawel Parys

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

2010

Efficient Evaluation of Nondeterministic Automata Using Factorization Forests.

Mikolaj Bojanczyk, Pawel Parys

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

XPath evaluation in linear time with polynomial combined complexity.

Pawel Parys

Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

Lower Bound for Evaluation of mu-nu Fixpoint.

Pawel Parys

Proceedings of the 6th Workshop on Fixed Points in Computer Science, 2009

2008

Systems of Equations Satisfied in All Commutative Finite Semigroups.

Pawel Parys

Proceedings of the Foundations of Software Science and Computational Structures, 2008

2006

Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders.

Krzysztof Onak, Pawel Parys

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006