Pawel Parys

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 54

Top Topics

Structured Data

Expressive Power

Transitive Closure

Top Venues

Publications

Anita Badyl, Pawel Parys
Extending the WMSO+U Logic with Quantification over Tuples. CSL (2024)
Damian Niwinski, Pawel Parys, Michal Skrzypczak
The Probabilistic Rabin Tree Theorem. CoRR (2023)
Damian Niwinski, Pawel Parys, Michal Skrzypczak
. LICS (2023)
Pawel Parys, Aleksander Wiacek
Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games. CoRR (2023)
Anita Badyl, Pawel Parys
Extending the WMSO+U Logic With Quantification Over Tuples. CoRR (2023)
Stefan Göller, Pawel Parys
Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete. SODA (2023)
Pawel Parys, Aleksander Wiacek
Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games. CiE (2023)
Pawel Parys
The Caucal hierarchy: Interpretations in the (W)MSO+U logic. Inf. Comput. 286 (2022)
David Barozzini, Pawel Parys, Jan Wroblewski
Unboundedness for Recursion Schemes: A Simpler Type System. ICALP (2022)
Karoliina Lehtinen, Pawel Parys, Sven Schewe, Dominik Wojtczak
A Recursive Approach to Solving Parity Games in Quasipolynomial Time. Log. Methods Comput. Sci. 18 (1) (2022)
David Barozzini, Pawel Parys, Jan Wroblewski
Unboundedness for Recursion Schemes: A Simpler Type System. CoRR (2022)
David Barozzini, Lorenzo Clemente, Thomas Colcombet, Pawel Parys
Cost Automata, Safe Schemes, and Downward Closures. Fundam. Informaticae 188 (3) (2022)
André Arnold, Damian Niwinski, Pawel Parys
A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation. CSL (2021)
Pawel Parys
Higher-Order Model Checking Step by Step. CoRR (2021)
Pawel Parys
Higher-Order Model Checking Step by Step. ICALP (2021)
Pawel Parys
Shelah-Stupp's and Muchnik's Iterations Revisited. CSR (2021)
Karoliina Lehtinen, Pawel Parys, Sven Schewe, Dominik Wojtczak
A Recursive Approach to Solving Parity Games in Quasipolynomial Time. CoRR (2021)
Pawel Parys
Compositionality of the MSO+U Logic. CoRR (2020)
Pawel Parys
Higher-Order Nonemptiness Step by Step. FSTTCS (2020)
David Barozzini, Lorenzo Clemente, Thomas Colcombet, Pawel Parys
Cost Automata, Safe Schemes, and Downward Closures. ICALP (2020)
Pawel Parys
On the Expressive Power of Higher-Order Pushdown Systems. Log. Methods Comput. Sci. 16 (3) (2020)
Pawel Parys
A Type System Describing Unboundedness. Discret. Math. Theor. Comput. Sci. 22 (4) (2020)
Pawel Parys
Parity Games: Another View on Lehtinen's Algorithm. CSL (2020)
Stefan Göller, Pawel Parys
Bisimulation Finiteness of Pushdown Systems Is Elementary. LICS (2020)
Pawel Parys
Higher-Order Nonemptiness Step by Step. CoRR (2020)
Stefan Göller, Pawel Parys
Bisimulation Finiteness of Pushdown Systems Is Elementary. CoRR (2020)
Pawel Parys
Recursion Schemes, the MSO Logic, and the U quantifier. Log. Methods Comput. Sci. 16 (1) (2020)
David Barozzini, Lorenzo Clemente, Thomas Colcombet, Pawel Parys
Cost Automata, Safe Schemes, and Downward Closures. CoRR (2020)
Pawel Parys
On the Expressive Power of Higher-Order Pushdown Systems. CoRR (2020)
Pawel Parys
Parity Games: Another View on Lehtinen's Algorithm. CoRR (2019)
Pawel Parys
Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time. CoRR (2019)
Wojciech Czerwinski, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdzinski, Ranko Lazic, Pawel Parys
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. SODA (2019)
Pawel Parys
Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time. MFCS (2019)
Pawel Parys
Extensions of the Caucal Hierarchy? LATA (2019)
Wojciech Czerwinski, Wim Martens, Matthias Niewerth, Pawel Parys
Minimization of Tree Patterns. J. ACM 65 (4) (2018)
Pawel Parys
Recursion Schemes, the MSO Logic, and the U quantifier. CoRR (2018)
Wojciech Czerwinski, Claire David, Filip Murlak, Pawel Parys
Reasoning about integrity constraints for tree-structured data. Theory Comput. Syst. 62 (4) (2018)
Pawel Parys
Intersection Types for Unboundedness Problems. DCM/ITRS (2018)
Pawel Parys
Homogeneity Without Loss of Generality. FSCD (2018)
Wojciech Czerwinski, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdzinski, Ranko Lazic, Pawel Parys
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. CoRR (2018)
Pawel Parys
Recursion Schemes and the WMSO+U Logic. STACS (2018)
Pawel Parys
Intersection Types and Counting. CoRR (2017)
Pawel Parys
The Complexity of the Diagonal Problem for Recursion Schemes. FSTTCS (2017)
Wojciech Czerwinski, Wim Martens, Matthias Niewerth, Pawel Parys
Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data. SIGMOD Rec. 46 (1) (2017)
Pawel Parys, Szymon Torunczyk
Models of Lambda-Calculus and the Weak MSO Logic. CSL (2016)
Lorenzo Clemente, Pawel Parys, Sylvain Salvati, Igor Walukiewicz
The Diagonal Problem for Higher-Order Recursion Schemes is Decidable. CoRR (2016)
Pawel Parys
Intersection Types and Counting. ITRS (2016)
Wojciech Czerwinski, Claire David, Filip Murlak, Pawel Parys
Reasoning About Integrity Constraints for Tree-Structured Data. ICDT (2016)
Pawel Parys
A characterization of lambda-terms transforming numerals. J. Funct. Program. 26 (2016)
Mikolaj Bojanczyk, Pawel Parys, Szymon Torunczyk
The MSO+U Theory of (N, <) Is Undecidable. STACS (2016)
Achim Blumensath, Thomas Colcombet, Pawel Parys
On a Fragment of AMSO and Tiling Systems. STACS (2016)
Lorenzo Clemente, Pawel Parys, Sylvain Salvati, Igor Walukiewicz
The Diagonal Problem for Higher-Order Recursion Schemes is Decidable. LICS (2016)
Wojciech Czerwinski, Wim Martens, Matthias Niewerth, Pawel Parys
Minimization of Tree Pattern Queries. PODS (2016)
Pawel Parys
Weak containment for partial words is coNP-complete. Inf. Process. Lett. 116 (2) (2016)
Mikolaj Bojanczyk, Pawel Parys, Szymon Torunczyk
The MSO+U theory of (N, <) is undecidable. CoRR (2015)
Wojciech Czerwinski, Wim Martens, Pawel Parys, Marcin Przybylko
The (Almost) Complete Guide to Tree Pattern Containment. PODS (2015)
Lorenzo Clemente, Pawel Parys, Sylvain Salvati, Igor Walukiewicz
Ordered Tree-Pushdown Systems. FSTTCS (2015)
Lorenzo Clemente, Pawel Parys, Sylvain Salvati, Igor Walukiewicz
Ordered Tree-Pushdown Systems. CoRR (2015)
Achim Blumensath, Thomas Colcombet, Denis Kuperberg, Pawel Parys, Michael Vanden Boom
Two-way cost automata and cost logics over infinite trees. CSL-LICS (2014)
Pawel Parys
How Many Numbers Can a Lambda-Term Contain? FLOPS (2014)
Pawel Parys
First-Order Logic on CPDA Graphs. CSR (2014)
Pawel Parys
Some results on complexity of µ-calculus evaluation in the black-box model. RAIRO Theor. Informatics Appl. 47 (1) (2013)
Alexander Kartzow, Pawel Parys
Strictness of the Collapsible Pushdown Hierarchy CoRR (2012)
Pawel Parys, Igor Walukiewicz
Weak Alternating Timed Automata Log. Methods Comput. Sci. 8 (3) (2012)
Pawel Parys
Higher-Order Pushdown Systems with Data GandALF (2012)
Pawel Parys
On the Significance of the Collapse Operation. LICS (2012)
Alexander Kartzow, Pawel Parys
Strictness of the Collapsible Pushdown Hierarchy. MFCS (2012)
Pawel Parys
A Pumping Lemma for Pushdown Graphs of Any Level. STACS (2012)
Vince Bárány, Mikolaj Bojanczyk, Diego Figueira, Pawel Parys
Decidable classes of documents for XPath. FSTTCS (2012)
Pawel Parys
Variants of Collapsible Pushdown Systems. CSL (2012)
Pawel Parys
Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata. STACS (2011)
Mikolaj Bojanczyk, Pawel Parys
XPath evaluation in linear time. J. ACM 58 (4) (2011)
Mikolaj Bojanczyk, Pawel Parys
Efficient Evaluation of Nondeterministic Automata Using Factorization Forests. ICALP (1) (2010)
Pawel Parys
Lower Bound for Evaluation of mu-nu Fixpoint. FICS (2009)
Pawel Parys, Igor Walukiewicz
Weak Alternating Timed Automata. ICALP (2) (2009)
Pawel Parys
XPath evaluation in linear time with polynomial combined complexity. PODS (2009)
Pawel Parys
Systems of Equations Satisfied in All Commutative Finite Semigroups. FoSSaCS (2008)
Mikolaj Bojanczyk, Pawel Parys
XPath evaluation in linear time. PODS (2008)
Krzysztof Onak, Pawel Parys
Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. FOCS (2006)