Publications

Paweł Parys

Number of publications: 65

2023

• David Barozzini, Lorenzo Clemente , Thomas Colcombet, Paweł Parys , Cost Automata, Safe Schemes, and Downward Closures, Fundamenta Informaticae, 188 (3) 2023, p. 127-178. See in PBN
• Paweł Parys , Aleksander Wiącek, Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games, Unity of Logic and Computation - 19th Conference on Computability in Europ, Batumi, Georgia, 24 July 2023 - 28 July 2023. See in PBN
• Damian Niwiński , Paweł Parys , Michał Skrzypczak , The Probabilistic Rabin Tree Theorem*, Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science, Boston, the United States of America, 26 June 2023 - 29 June 2023. See in PBN
• Stefan Göller, Paweł Parys , Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete, 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Florencja, Italy, 22 January 2023 - 25 January 2023. See in PBN

2022

• Karoliina Lehtinen, Paweł Parys , Sven Schewe, Dominik Wojtczak, A Recursive Approach to Solving Parity Games in Quasipolynomial Time, Logical Methods in Computer Science, 18 (1) 2022, p. 8:1-8:18. See in PBN
• Paweł Parys , The Caucal hierarchy: Interpretations in the (W)MSO+U logic, Information and Computation, 286 2022, p. 104782. See in PBN
• David Barozzini, Paweł Parys , Jan Wroblewski, Unboundedness for Recursion Schemes: A Simpler Type System, 49th International Colloquium on Automata, Languages and Programming, Paris, France, 4 July 2022 - 8 July 2022, 229 2022, p. 112:1--112:19. See in PBN

2021

• André Arnold, Damian Niwiński , Paweł Parys , A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation, 29th EACSL Annual Conference on Computer Science Logic, Lublana, Slovenia, 25 January 2021 - 28 January 2021, 183 2021, p. 9:1--9:23. See in PBN
• Paweł Parys , Higher-Order Model Checking Step by Step, 48th International Colloquium on Automata, Languages and Programming, Glasgow, the United Kingdom of Great Britain and Northern Ireland, 12 July 2021 - 16 July 2021, 198 2021, p. 140:1--140:16. See in PBN
• Paweł Parys , Shelah-Stupp's and Muchnik's Iterations Revisited, 16th International Computer Science Symposium in Russia, Soczi, the Russian Federation, 28 June 2021 - 2 July 2021, 12730 2021, p. 395--405. See in PBN

2020

• Paweł Parys , A Type System Describing Unboundedness, Discrete Mathematics and Theoretical Computer Science, 22 (4) 2020. See in PBN
• Stefan Göller, Paweł Parys , Bisimulation Finiteness of Pushdown Systems Is Elementary, Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, 8 July 2020 - 11 July 2020. See in PBN
• David Barozzini, Lorenzo Clemente , Thomas Colcombet, Paweł Parys , Cost Automata, Safe Schemes, and Downward Closures, 47th International Colloquium on Automata, Languages and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020, 168 2020, p. 109:1-109:18. See in PBN
• Paweł Parys , Higher-Order Nonemptiness Step by Step, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, Goa, India, 14 December 2020 - 18 December 2020, 182 2020, p. 53:1-53:14. See in PBN
• Paweł Parys , On the Expressive Power of Higher-Order Pushdown Systems, Logical Methods in Computer Science, 16 (3) 2020. See in PBN
• Paweł Parys , Parity Games: Another View on Lehtinen's Algorithm, 28th International Conference on Computer Science Logic, Barcelona, Spain, 13 January 2020 - 16 January 2020, 152 2020, p. 32:1-32:15. See in PBN
• Paweł Parys , Recursion Schemes, the MSO Logic, and the U quantifier, Logical Methods in Computer Science, 16 (1) 2020. See in PBN

2019

• Paweł Parys , Extensions of the Caucal Hierarchy?, 13th International Conference on Language and Automata Theory and Applications, Saint Petersburg, the Russian Federation, 26 March 2019 - 29 March 2019. See in PBN
• Paweł Parys , Intersection Types for Unboundedness Problems, Electronic Proceedings in Theoretical Computer Science, 293 2019, p. 7-27. See in PBN
• Paweł Parys , Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, Aachen, Germany, 26 August 2019 - 30 August 2019. See in PBN
• Wojciech Czerwiński , Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdziński, Ranko Lazić, Paweł Parys , Universal Trees Grow Inside Separating Automata: Quasi-Polynomial Lower Bounds for Parity Games, 30th ACM-SIAM Symposium on Discrete Algorithms, San Diego, the United States of America, 6 January 2019 - 9 January 2019. See in PBN

2018

• Paweł Parys , Homogeneity Without Loss of Generality, 3rd International Conference on Formal Structures for Computation and Deduction, FSCD 2018, Oxford, the United Kingdom of Great Britain and Northern Ireland, 9 July 2018 - 12 July 2018. See in PBN
• Wojciech Czerwiński , Wim Martens, Matthias Niewerth, Paweł Parys , Minimization of Tree Patterns, Journal of the ACM, 65 (4) 2018, p. 26:1-26:46. See in PBN
• Wojciech Czerwiński , Claire David, Filip Murlak , Paweł Parys , Reasoning About Integrity Constraints for Tree-Structured Data, Theory of Computing Systems, 62 (4) 2018, p. 941–976. See in PBN
• Paweł Parys , Recursion Schemes and the WMSO+U Logic, The 35th International Symposium on Theoretical Aspects of Computer Science, Caen, France, 28 February 2018 - 3 March 2018. See in PBN
• Paweł Parys , The Complexity of the Diagonal Problem for Recursion Schemes, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Kanpur, India, 11 December 2017 - 15 December 2017. See in PBN

2017

• Damian Niwiński , Henryk Michalewski , Wojciech Rytter , Joost Winter, Michał Skrzypczak , Szymon Toruńczyk , Michał Pilipczuk , Eryk Kopczyński , Sławomir Lasota , Paweł Parys , Joanna Ochremiak, Wojciech Czerwiński , Bartosz Klin , Igor Walukiewicz, Szczepan Hummel, Mikołaj Bojańczyk , Piotr Hofman , Lorenzo Clemente , Filip Mazowiecki, Filip Murlak , 200 Problems in Formal Languages and Automata Theory, 2017. See in PBN
• Paweł Parys , Intersection Types and Counting, Eighth Workshop on Intersection Types and Related Systems, Porto, Portugal, 26 June 2016 - 26 June 2016. See in PBN
• Wojciech Czerwiński , Wim Martens, Matthias Niewerth, Paweł Parys , Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data, SIGMOD Record, 46 (1) 2017, p. 15–22. See in PBN

2016

• Paweł Parys , A Characterization of Lambda-Terms Transforming Numerals, Journal of Functional Programming, 2016. See in PBN
• Wojciech Czerwiński , Wim Martens, Matthias Niewerth, Paweł Parys , Minimization of Tree Pattern Queries, 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, San Francisco, the United States of America, 26 June 2016 - 1 July 2016. See in PBN
• Paweł Parys , Szymon Toruńczyk , Models of Lambda-Calculus and the Weak MSO Logic, 25th EACSL Annual Conference on Computer Science Logic, Marseille, France, 29 August 2016 - 1 September 2016. See in PBN
• Achim Blumensath, Thomas Colcombet, Paweł Parys , On a Fragment of AMSO and Tiling Systems, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orlean, France, 17 February 2016 - 20 February 2016. See in PBN
• Wojciech Czerwiński , Paweł Parys , Filip Murlak , Claire David, Reasoning About Integrity Constraints for Tree-Structured Data, 19th International Conference on Database Theory, Bordeaux, France, 15 March 2016 - 18 March 2016. See in PBN
• Paweł Parys , Sylvain Salvati, Igor Walukiewicz, Lorenzo Clemente , The Diagonal Problem for Higher-Order Recursion Schemes is Decidable, 31st Annual ACM/IEEE Symposium on Logic in Computer Science, New York, the United States of America, 5 July 2016 - 8 July 2016. See in PBN
• Mikołaj Bojańczyk , Paweł Parys , Szymon Toruńczyk , The MSO+U Theory of (N,<) Is Undecidable, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orlean, France, 17 February 2016 - 20 February 2016. See in PBN
• Paweł Parys , Weak Containment for Partial Words is coNP-Complete, Information Processing Letters, 2016. See in PBN

2015

• Igor Walukiewicz, Paweł Parys , Sylvain Salvati, Lorenzo Clemente , Ordered Tree-Pushdown Systems, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015), Bangalore, India, 16 December 2015 - 18 December 2015. See in PBN
• Wojciech Czerwiński , Wim Martens, Paweł Parys , Marcin Przybyłko, The (Almost) Complete Guide to Tree Pattern Containment, 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015, Melbourne, Australia, 31 May 2015 - 4 June 2015. See in PBN

2014

• Paweł Parys , First-Order Logic on CPDA Graphs, Computer Science - Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014, Moscow, the Russian Federation, 7 June 2014 - 11 June 2014. See in PBN
• Paweł Parys , How Many Numbers Can a Lambda-Term Contain?, Functional and Logic Programming - 12th International Symposium, FLOPS 2014, Kanazawa, Japan, June 4-6, 2014, Kanazawa, Japan, 4 June 2014 - 6 June 2014. See in PBN
• Achim Blumensath, Thomas Colcombet, Denis Kuperberg, Paweł Parys , Michael Vanden Boom, Two-Way Cost Automata and Cost Logics Over Infinite Trees, 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), CSL-LICS '14, Vienna, Austria, July 14 - 18, 2014, Vienna, Austria, 14 July 2014 - 18 July 2014. See in PBN

2013

• Paweł Parys , Some results on complexity of µ-calculus evaluation in the black-box model, RAIRO - Theoretical Informatics and Applications, 47 (1) 2013, p. 97-109. See in PBN

2012

• Paweł Parys , A Pumping Lemma for Pushdown Graphs of Any Level, 2012. See in PBN
• Mikołaj Bojańczyk , Vince Bárány, Diego Figueira, Paweł Parys , Decidable Classes of Documents for XPath, 2012. See in PBN
• Paweł Parys , Higher-Order Pushdown Systems With Data, 2012. See in PBN
• Paweł Parys , On the Significance of the Collapse Operation, 2012. See in PBN
• Alexander Kartzow, Paweł Parys , Strictness of the Collapsible Pushdown Hierarchy, 2012. See in PBN
• Paweł Parys , Variants of Collapsible Pushdown Systems, 2012. See in PBN
• Paweł Parys , Igor Walukiewicz, Weak Alternating Timed Automata, Logical Methods in Computer Science, 2012. See in PBN

2011

• Paweł Parys , Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata, 2011. See in PBN
• Paweł Parys , Variants of Collapsible Pushdown Systems, 2011. See in PBN
• Mikołaj Bojańczyk , Paweł Parys , XPath Evaluation in Linear Time, Journal of the ACM, 2011. See in PBN

2010

• Mikołaj Bojańczyk , Paweł Parys , Efficient Evaluation of Nondeterministic Automata Using Factorization Forests, Lecture Notes in Computer Science, 2010. See in PBN
• Paweł Parys , Some Results on Complexity of Mu-Calculus Evaluation in the Black-Box Model, Logical Approaches to Barriers in Computing and Complexity, Greifswald, Germany, 17 February 2010 - 20 February 2010. See in PBN
• Alexander Kartzow, Paweł Parys , Strictness of the Collapsible Pushdown Hierarchy, 2010. See in PBN

2009

• Paweł Parys , Lower Bound for Evaluation of mu-nu Fixpoint, 6th Workshop on Fixed Points in Computer Science, 2009. See in PBN
• Paweł Parys , Igor Walukiewicz, Weak Alternating Timed Automata, Lecture Notes in Computer Science, 2009. See in PBN
• Paweł Parys , XPath Evaluation in Linear Time With Polynomial Combined Complexity, 2009. See in PBN

2008

• Paweł Parys , On the Significance of the Collapse Operation, 2008. See in PBN
• Paweł Parys , Systems of Equations Satisfied in All Commutative Finite Semigroups., 2008. See in PBN
• Mikołaj Bojańczyk , Paweł Parys , XPath Evaluation in Linear Time, 2008. See in PBN

2006

• Krzysztof Onak, Paweł Parys , Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Berkeley, the United States of America, 21 October 2006 - 24 October 2006. See in PBN

2004

• Wojciech Legierski, Paweł Parys , Planowanie zajęć metodami programowania z ograniczeniami, 2004. See in PBN

2003

• Wojciech Legierski, Paweł Parys , System for Solving Timetabling Problems, AI-METH 2003 Symposium on Methods of Artificial Intelligence, Gliwice, Poland, 5 November 2003 - 7 November 2003. See in PBN