Publications

Infinite trees

• Niwiński D., Parys P., Skrzypczak M.: A Dichotomy Theorem for Ordinal Ranks in MSO - on STACS 2025 [longer slides / shorter slides]
• Niwiński D., Parys P., Skrzypczak M.: The Probabilistic Rabin Tree Theorem - on LICS 2023 [longer slides / shorter slides]

Pushdown automata

• Göller S., Parys P.: Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete on SODA 2023 [slides: shorter / longer]
• Göller S., Parys P.: Bisimulation Finiteness of Pushdown Systems Is Elementary - on LICS 2020

Higher-order recursion & unboundedness

• Badyl A., Parys P.: Extending the WMSO+U Logic with Quantification over Tuples - on CSL 2024 [slides]
• Barozzini D., Parys P., Wróblewski J.: Unboundedness for Recursion Schemes: A Simpler Type System - on ICALP 2022 [slides]
• Parys P.: The Caucal Hierarchy: Interpretations in the (W)MSO+U Logic - in Information and Computation
• Barozzini D., Clemente L., Colcombet T., Parys P.: Cost Automata, Safe Schemes, and Downward Closures - best paper on ICALP 2020
• Parys P.: Intersection Types for Unboundedness Problems - in Electronic Proceedings in Theoretical Computer Science
• Parys P.: Extensions of the Caucal Hierarchy? - on LATA 2019 [slides]
• Parys P.: Recursion Schemes, the MSO Logic, and the U quantifier - in Logical Methods in Computer Science
• Parys P.: Recursion Schemes and the WMSO+U Logic (longer version) - on STACS 2018 [slides - version 1 / version 2 / version 3]
• Parys P.: A Type System Describing Unboundedness - in DMTCS
• Parys P.: Complexity of the Diagonal Problem for Recursion Schemes (longer version) - on FSTTCS 2017 [slides]
• Parys P.: Intersection Types and Counting (longer version) - on ITRS 2016 [slides - version 1 / version 2]
• Clemente L., Parys P., Salvati S., Walukiewicz I.: The Diagonal Problem for Higher-Order Recursion Schemes is Decidable - on LICS 2016
• Parys P.: A Characterization of Lambda-terms Transforming Numerals - in Journal of Functional Programming [slides]
• Parys P.: How Many Numbers Can a Lambda-term Contain? (longer version) - on FLOPS 2014 [slides]

Fixed points / mu-calculus / parity games

• Lehtinen K., Parys P., Schewe S., Wojtczak D.: A Recursive Approach to Solving Parity Games in Quasipolynomial Time - in LMCS
• Parys P., Wiącek A.: Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games - on CiE 2023 [slides]
• Arnold A., Niwiński D., Parys P.: A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation - on CSL 2021 [shorter slides / longer slides]
• Parys P.: Parity Games: Another View on Lehtinen's Algorithm - on CSL 2020 [slides]
• Parys P.: Parity Games: Zielonka's Algorithm in Quasi-polynomial Time - best paper on MFCS 2019 [short slides / longer slides / poster]
• Czerwiński W., Daviaud L., Fijalkow N., Jurdziński M., Lazić R., Parys P.: Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games - on SODA 2019 [slides / poster]
• Parys P.: Some Results on Complexity of mu-calculus Evaluation in the Black-box Model
  • short version, on LABCC workshop 2010
  • journal version, in RAIRO - Theoretical Informatics and Applications (2013)
• Parys P.: Evaluation of normalized mu-calculus formulas is polynomial for fixed structure size - unpublished (2009)
• Parys P.: Lower bound for evaluation of mu-nu fixpoint on FICS workshop 2009 [slides]

Higher-order recursion

• Parys P.: Higher-Order Model Checking Step by Step - on ICALP 2021 [slides]
• Parys P.: Shelah-Stupp's and Muchnik's Iterations Revisited - on CSR 2021 [slides]
• Parys P.: Higher-Order Nonemptiness Step by Step - on FSTTCS 2020 [slides]
• Parys P.: Homogeneity without Loss of Generality - on FSCD 2018 [slides]
• Parys P.: Introduction to Collapsible Pushdown Automata and Higher-Order Recursion Schemes [slides]
• Parys P., Toruńczyk S.: Models of Lambda-Calculus and the Weak MSO Logic - on CSL 2016
• Clemente L., Parys P., Salvati S., Walukiewicz I.: Ordered Tree-Pushdown Systems - on FSTTCS 2015
• Parys P.: First-Order Logic on CPDA Graphs (longer version) - on CSR 2014 [slides]
• Parys P.: On the Expressive Power of Higher-Order Pushdown Systems - submitted to Logical Methods in Computer Science
• Parys P.: Higher-Order Pushdown Systems with Data - on GandALF 2012 [slides]
• Parys P.: Variants of Collapsible Pushdown Systems - on CSL 2012 [slides]
• Kartzow A., Parys P.: Strictness of the Collapsible Pushdown Hierarchy - on MFCS 2012
• Parys P.: On the Significance of the Collapse Operation - on LICS 2012 [slides / slides in polish / longer slides]
• Parys P.: A Pumping Lemma for Pushdown Graphs of Any Level - on STACS 2012 [slides]
• Parys P.: The pumping lemma is incorect? version 1 version 2 - unpublished (2010)
• Parys P.: Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata on STACS 2011 [slides - version 1 / version 2 / version 3]
• Parys P.: Higher Order Stacks Cannot Replace Nondeterminism - unpublished (2010)

Automata with counters, MSO+U, etc.

• Parys P.: Compositionality of the MSO+U Logic (2020)
• Bojańczyk M., Parys P., Toruńczyk M.: The MSO+U Theory of (N,<) Is Undecidable - on STACS 2016 [slides - long / short]
• Blumensath A., Colcombet T., Parys P.: On a Fragment of AMSO and Tiling Systems - on STACS 2016 [slides]
• Blumensath A., Colcombet T., Kuperberg D., Parys P., Vanden Boom M.: Two-Way Cost Automata and Cost Logics over Infinite Trees - on CSL-LICS 2014

Data trees / XPath

• Czerwiński W., Martens W., Niewerth M., Parys P.: Minimization of Tree Pattern Queries [slides]
  • conference version - on PODS 2016
  • journal version (Minimization of Tree Patterns) - in Journal of the ACM
  • short version (Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data) - in SIGMOD Record
• Czerwiński W., David C., Murlak F., Parys P.: Reasoning About Integrity Constraints for Tree-Structured Data
  • conference version - on ICDT 2016
  • journal version - in Theory of Computing Systems
• Parys P.: Weak Containment for Partial Words is coNP-complete - in Information Processing Letters
• Czerwiński W., Martens W., Parys P., Przybyłko M.: The (Almost) Complete Guide to Tree Pattern Containment - on PODS 2015
• Barany V., Bojańczyk M., Figueira D., Parys P.: Decidable classes of documents for XPath - on FSTTCS 2012 [slides]
• Parys P.: Application of Automata Theory to Processing of XML Documents (PhD dissertation, 2011) [slides in polish / in english]
• Implementation of the algorithm realized by Kamil Kawka
• Bojańczyk M., Parys P.: Efficient Evaluation of Nondeterministic Automata Using Factorization Forests on ICALP 2010 [slides - long / short]
• Bojańczyk M., Parys P.: XPath Evaluation in Linear Time in Journal of the ACM (2009-2011)
• Parys P.: XPath Evaluation in Linear Time with Polynomial Combined Complexity - on PODS 2009 (Best Student Paper Award) [slides / more slides]
• Bojańczyk M., Parys P.: XPath Evaluation in Linear Time on PODS 2008 [slides]

Timed automata

• Parys P., Walukiewicz I.: Weak Alternating Timed Automata
  • conference version, on ICALP 2009
  • full version, HAL (2009)
  • journal version, in LMCS (2012)

Tutorials

• Parys P.: Maximum Matchings via Algebraic Methods for Beginners - unpublished tutorial (2009)
• Parys P.: Złożoność informacyjna Kołmogorowa - slides in polish (2012)

Other small things

• Parys P.: The Problems of Reachability in a Petri Net and Emptiness of Intersection of Commutative Languages Are Equivalent (short note, 2009)
• Parys P.: Systems of Equations Satisfied in All Commutative Finite Semigroups on FoSSaCS 2008
• Praca magisterska: Parys P.: Układy równań spełnione we wszystkich przemiennych półgrupach skończonych (2007)
• Onak K., Parys P.: Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders on the 47th Annual Symposium on Foundations of Computer Science (FOCS 2006)
• My bachelor project in mathematics: Parys P.: Differentiable Functions with Large Sets of Critical Values (2005)
• Legierski W., Parys P.: Planowanie zajęć metodami programowania z ograniczeniami (Solving Timetable Problems Using Constraint Programming) In: ,,Automatyzacja Procesów Dyskretnych, tom: Optymalizacja Dyskretna. Robotyka i sterowniki programowalne'', WNT, 2004, pages 125-132 and on: Krajowa Konferencja Automatyki Procesów Dyskretnych, Zakopane 2004 and on: AI-METH 2003 Symposium on Methods of Artificial Intelligence, Gliwice 2003

Legend:

• Published (listed by DBLP)
• Minor
• Unpublished

Licznik: 3622