Publications

Michał Skrzypczak

Number of publications: 51

2024

• Pierre Ohlmann, Michał Skrzypczak , Positionality in Σ⁰₂ and a Completeness Result, 41st International Symposium on Theoretical Aspects of Computer Science, Clermont-Ferrand, France, 12 March 2024 - 14 March 2024. See in PBN
• Nathan Lhote, Vincent Michielini , Michał Skrzypczak , Uniformisation of Regular Relations in First-Order Logic with Two Variables, 39th Annual ACM/IEEE Symposium on Logic in Computer Science, Tallinn, Estonia, 8 July 2024 - 11 July 2024, 8 2024, p. 1-13. See in PBN

2023

• Wojciech Czerwiński , Maciej Dębski, Tomasz Gogacz , Gordon Ho, Sanjay Jain, Michał Skrzypczak , Frank Stephan, Christopher Tan, Languages Given by Finite Automata over the Unary Alphabet, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India, 18 December 2023 - 20 December 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

2022

• Olivier Finkel, Michał Skrzypczak , On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words, Fundamenta Informaticae, 183 (3-4) 2022, p. 243-291. See in PBN

2021

• Lorenzo Clemente , Michał Skrzypczak , Deterministic and Game Separability for Regular Languages of Infinite Trees, 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. 126:1--126:15. See in PBN
• Damian Niwiński , Michał Skrzypczak , On Guidable Index of Tree Automata, 46th International Symposium on Mathematical Foundations of Computer Science, Tallinn, Estonia, 23 August 2021 - 27 August 2021, 202 2021, p. 81:1--81:14. See in PBN
• Piotr Hofman , Michał Skrzypczak , Preface, Fundamenta Informaticae, 180 (4) 2021, p. i-ii. See in PBN
• Marcin Przybyłko, Michał Skrzypczak , The uniform measure of simple regular sets of infinite trees, Information and Computation, 278 2021, p. 104595,1-24. See in PBN

2020

• Damian Niwiński , Marcin Przybyłko, Michał Skrzypczak , Computing Measures of Weak-MSO Definable Sets of Trees, 47th International Colloquium on Automata, Languages, and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020, 168 2020, p. 136:1--136:18. See in PBN
• Udi Boker, Denis Kuperberg, Michał Skrzypczak , Karoliina Lehtinen, On the Succinctness of Alternating Parity Good-For-Games Automata, Leibniz International Proceedings in Informatics, 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. 41:1--41:13. See in PBN
• Vincent Michielini , Michał Skrzypczak , Regular Choice Functions and Uniformisations For countable Domains, 45th International Symposium on Mathematical Foundations of Computer Science, Prague, Czechia, 24 August 2020 - 28 August 2020, 170 2020, p. 69:1--69:13. See in PBN
• Grzegorz Fabiański , Michał Skrzypczak , Szymon Toruńczyk , Uniformisations of Regular Relations Over Bi-Infinite Words, Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, 8 July 2020 - 11 July 2020. See in PBN

2019

• Michał Skrzypczak , Piotr Hofman , 23rd international conference, DLT 2019, Warsaw, Poland, August 5-9, 2019, proceedings, 23nd International Conference on Developments in Language Theory, Warsaw, Poland, 4 August 2019 - 8 August 2019. See in PBN
• Mikołaj Bojańczyk , Edon Kelmendi, Michał Skrzypczak , MSO+∇ is undecidable, Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science, Vancouver, Canada, 24 July 2019 - 27 July 2019. See in PBN
• Mikołaj Bojańczyk , Filippo Cavallari, Thomas Place, Michał Skrzypczak , Regular tree languages in low levels of the Wadge Hierarchy, Logical Methods in Computer Science, 15 (3) 2019, p. 27:1–27:61. See in PBN
• Leszek Kołodziejczyk , Henryk Michalewski , Pierre Pradic, Michał Skrzypczak , The logical strength of Büchi's decidability theorem, Logical Methods in Computer Science, 15 (2) 2019, p. 16:1-16:31. See in PBN
• Nathan Lhote, Vincent Michielini , Michał Skrzypczak , Uniformisation Gives the Full Strength of Regular Languages, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, Aachen, Germany, 26 August 2019 - 30 August 2019, 138 2019, p. 61:1--61:13. See in PBN

2018

• Michał Skrzypczak , B\üchi VASS Recognise \(\sum\)\(^\mbox1\)\(_\mbox1\)-complete \(ω\)-languages, Reachability Problems, Marsylia, France, 24 September 2018 - 26 September 2018. See in PBN
• Udi Boker, Orna Kupferman, Michał Skrzypczak , How Deterministic are Good-For-Games Automata?, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Kanpur, India, 11 December 2017 - 15 December 2017. See in PBN
• Matteo Mio, Michał Skrzypczak , Henryk Michalewski , Monadic Second Order Logic with Measure and Category Quantifiers, Logical Methods in Computer Science, 14 (2) 2018, p. 2:1-2:29. See in PBN
• Henryk Michalewski , Michał Skrzypczak , On the Strength of Unambiguous Tree Automata, International Journal of Foundations of Computer Science, 29 (5) 2018, p. 911-933. See in PBN
• Michał Skrzypczak , Unambiguous Languages Exhaust the Index Hierarchy, 45th International Colloquium on Automata, Languages, and Programming, Praha, Czechia, 9 July 2018 - 13 July 2018. 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
• Filippo Cavallari, Henryk Michalewski , Michał Skrzypczak , A Characterisation of Pi^0_2 Regular Tree Languages, 42nd International Symposium on Mathematical Foundations of Computer Science, Aalborg, Denmark, 21 August 2017 - 25 August 2017. See in PBN
• Michał Skrzypczak , Connecting Decidability and Complexity for MSO Logic, 21st International Conference on Developments in Language Theory, Liege, Belgium, 7 August 2017 - 11 August 2017. See in PBN
• Tomasz Gogacz, Matteo Mio, Michał Skrzypczak , Henryk Michalewski , Measure properties of regular sets of trees, Information and Computation, 256 2017, p. 108-130. See in PBN

2016

• Michał Skrzypczak , Igor Walukiewicz, Deciding the Topological Complexity of Büchi Languages, 43rd International Colloquium on Automata, Languages, and Programming, 2016. See in PBN
• Michał Skrzypczak , Descriptive Set Theoretic Methods in Automata Theory - Decidability and Topological Complexity, 2016. See in PBN
• Filip Murlak , Michał Skrzypczak , Alessandro Facchini, Index Problems for Game Automata, ACM Transactions on Computational Logic, 17 (4) 2016, p. 24:1-24:38. See in PBN
• Marcin Przybyłko, Michał Skrzypczak , On the Complexity of Branching Games with Regular Conditions, Mathematical Foundations of Computer Science 2016, Kraków, Poland, 2016. See in PBN
• Leszek Kołodziejczyk , Henryk Michalewski , Pierre Pradic, Michał Skrzypczak , The logical strength of Büchi's decidability theorem, 25th EACSL Annual Conference on Computer Science Logic, Marsylia, France, 29 August 2016 - 1 September 2016. See in PBN
• Henryk Michalewski , Michał Skrzypczak , Unambiguous Büchi Is Weak, Developments in Language Theory, Montreal, Canada, 2016. See in PBN

2015

• Nathanael Fijalkow, Michał Skrzypczak , Irregular Behaviours for Probabilistic Automata, Reachability Problems, Warsaw, Poland, 2015. See in PBN
• Denis Kuperberg, Michał Skrzypczak , On Determinisation of Good-For-Games Automata, Automata, Languages, and Programming - 42th International Colloquium, Kyoto, Japan, 6 July 2015 - 10 July 2015. See in PBN
• Alessandro Facchini, Filip Murlak , Michał Skrzypczak , On the Weak Index Problem for Game Automata, 22nd International Workshop on Logic, Language, Information, and Computation, 2015, p. 93-108. See in PBN
• Mikołaj Bojańczyk , Tomasz Idziaszek, Michał Skrzypczak , Regular languages of thin trees, Theory of Computing Systems, 2015. See in PBN
• Nathanael Fijalkow, Florian Horn, Denis Kuperberg, Michał Skrzypczak , Trading bounds for memory in games with counters, Automata, Languages, and Programming - 42th International Colloquium, Kyoto, Japan, 6 July 2015 - 10 July 2015. See in PBN

2014

• Tomasz Gogacz, Henryk Michalewski , Matteo Mio, Michał Skrzypczak , Measure Properties of Game Tree Languages, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, Budapest, Hungary, 25 August 2014 - 29 August 2014. See in PBN
• Mikołaj Bojańczyk , Tomasz Gogacz, Henryk Michalewski , Michał Skrzypczak , On the Decidability of MSO+U on Infinite Trees, International Colloquium on Automata, Languages and Programming, 2014. See in PBN
• Olivier Finkel, Michał Skrzypczak , On the Topological Complexity of w-Languages of Non-Deterministic Petri Nets, Information Processing Letters, 2014. See in PBN
• Michał Skrzypczak , Separation Property for wB- and wS-regular Languages, Logical Methods in Computer Science, 10 (1:8) 2014, p. 1-20. See in PBN

2013

• Udi Boker, Denis Kuperberg, Orna Kupferman, Michał Skrzypczak , Nondeterminism in the Presence of a Diverse or Unknown Future, Automata, Languages, and Programming - 40th International Colloquium, Riga, Latvia, 2013. See in PBN
• Alessandro Facchini, Filip Murlak , Michał Skrzypczak , Rabin-Mostowski Index Problem: A Step beyond Deterministic Automata, Twenty-Eighth Annual ACM/IEEE Symposium on LOGIC IN COMPUTER SCIENCE, New Orleans, LA, the United States of America, 25 June 2013 - 28 June 2013. See in PBN
• Mikołaj Bojańczyk , Tomasz Idziaszek, Michał Skrzypczak , Regular languages of thin trees, 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, Kiel, Germany, 27 February 2013 - 2 March 2013. See in PBN
• Michał Skrzypczak , Topological extension of parity automata, Information and Computation, 228 2013, p. 16-27. See in PBN
• Marcin Bilkowski, Michał Skrzypczak , Simona Ronchi Della Rocca, Unambiguity and uniformization problems on infinite trees, Computer Science Logic 2013, 2013, p. 81-100. See in PBN

2012

• Szczepan Hummel, Michał Skrzypczak , The Topological Complexity of MSO+U and Related Automata Models, Fundamenta Informaticae, 2012. See in PBN
• Szczepan Hummel, Michał Skrzypczak , Topological Complexity of MSO+U and Related Automata Models, Lecture Notes in Computer Science, 2012. See in PBN

2010

• Mikołaj Bojańczyk , Damian Niwiński , Alexander Rabinovich, Adam Radziwonczyk-Syta, Michał Skrzypczak , On the Borel Complexity of MSO Definable Sets of Branches, Fundamenta Informaticae, 2010. See in PBN
• Szczepan Hummel, Michał Skrzypczak , Szymon Toruńczyk , On the Topological Complexity of MSO+U and Related Automata Models, Mathematical Foundations of Computer Science 2010, Brno, Czechia, 2010. See in PBN