Michal Skrzypczak

According to our database, Michal Skrzypczak authored at least 54 papers between 2010 and 2024.

Collaborative distances:

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

2024

Positionality in Σ⁰₂ and a Completeness Result.

Pierre Ohlmann, Michal Skrzypczak

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Uniformisation of Regular Relations in First-Order Logic with Two Variables.

Nathan Lhote, Vincent Michielini, Michal Skrzypczak

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

2023

Positionality in Σ_0^2 and a completeness result.

Pierre Ohlmann, Michal Skrzypczak

CoRR, 2023

The Probabilistic Rabin Tree Theorem.

Damian Niwinski, Pawel Parys, Michal Skrzypczak

CoRR, 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

Languages Given by Finite Automata over the Unary Alphabet.

Wojciech Czerwinski, Maciej Debski, Tomasz Gogasz, Gordon Hoi, Sanjay Jain, Michal Skrzypczak, Frank Stephan, Christopher Tan

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

2021

The uniform measure of simple regular sets of infinite trees.

Marcin Przybylko, Michal Skrzypczak

Inf. Comput., 2021

Preface.

Michal Skrzypczak, Piotr Hofman

Fundam. Informaticae, 2021

On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words.

Olivier Finkel, Michal Skrzypczak

Fundam. Informaticae, 2021

Unambiguity in Automata Theory (Dagstuhl Seminar 21452).

Thomas Colcombet, Karin Quaas, Michal Skrzypczak

Dagstuhl Reports, 2021

On Guidable Index of Tree Automata.

Damian Niwinski, Michal Skrzypczak

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Deterministic and Game Separability for Regular Languages of Infinite Trees.

Lorenzo Clemente, Michal Skrzypczak

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

2020

On Succinctness and Recognisability of Alternating Good-for-Games Automata.

Udi Boker, Denis Kuperberg, Karoliina Lehtinen, Michal Skrzypczak

CoRR, 2020

Regular Choice Functions and Uniformisations For countable Domains.

Vincent Michielini, Michal Skrzypczak

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Uniformisations of Regular Relations Over Bi-Infinite Words.

Grzegorz Fabianski, Michal Skrzypczak, Szymon Torunczyk

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

Computing Measures of Weak-MSO Definable Sets of Trees.

Damian Niwinski, Marcin Przybylko, Michal Skrzypczak

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

On the Succinctness of Alternating Parity Good-For-Games Automata.

Udi Boker, Denis Kuperberg, Karoliina Lehtinen, Michal Skrzypczak

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

2019

The logical strength of Büchi's decidability theorem.

Leszek Aleksander Kolodziejczyk, Henryk Michalewski, Cécilia Pradic, Michal Skrzypczak

Log. Methods Comput. Sci., 2019

Regular tree languages in low levels of the Wadge Hierarchy.

Mikolaj Bojanczyk, Filippo Cavallari, Thomas Place, Michal Skrzypczak

Log. Methods Comput. Sci., 2019

MSO+nabla is undecidable.

Mikolaj Bojanczyk, Edon Kelmendi, Michal Skrzypczak

CoRR, 2019

Uniformisation Gives the Full Strength of Regular Languages.

Nathan Lhote, Vincent Michielini, Michal Skrzypczak

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

MSO+∇ is undecidable.

Mikolaj Bojanczyk, Edon Kelmendi, Michal Skrzypczak

Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, 2019

2018

Monadic Second Order Logic with Measure and Category Quantifiers.

Matteo Mio, Michal Skrzypczak, Henryk Michalewski

Log. Methods Comput. Sci., 2018

On the Strength of Unambiguous Tree Automata.

Henryk Michalewski, Michal Skrzypczak

Int. J. Found. Comput. Sci., 2018

Büchi VASS Recognise ∑¹₁-complete ω-languages.

Michal Skrzypczak

Proceedings of the Reachability Problems - 12th International Conference, 2018

Unambiguous Languages Exhaust the Index Hierarchy.

Michal Skrzypczak

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Measure properties of regular sets of trees.

Tomasz Gogacz, Henryk Michalewski, Matteo Mio, Michal Skrzypczak

Inf. Comput., 2017

Büchi VASS recognise w-languages that are Sigma^1_1 - complete.

Michal Skrzypczak

CoRR, 2017

A Characterisation of Pi^0_2 Regular Tree Languages.

Filippo Cavallari, Henryk Michalewski, Michal Skrzypczak

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

How Deterministic are Good-For-Games Automata?.

Udi Boker, Orna Kupferman, Michal Skrzypczak

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

Connecting Decidability and Complexity for MSO Logic.

Michal Skrzypczak

Proceedings of the Developments in Language Theory - 21st International Conference, 2017

2016

Descriptive Set Theoretic Methods in Automata Theory - Decidability and Topological Complexity

Michal Skrzypczak

Lecture Notes in Computer Science 9802, Springer, ISBN: 978-3-662-52947-8, 2016

Index Problems for Game Automata.

Alessandro Facchini, Filip Murlak, Michal Skrzypczak

ACM Trans. Comput. Log., 2016

Regular Languages of Thin Trees.

Tomasz Idziaszek, Michal Skrzypczak, Mikolaj Bojanczyk

Theory Comput. Syst., 2016

On the Complexity of Branching Games with Regular Conditions.

Marcin Przybylko, Michal Skrzypczak

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Deciding the Topological Complexity of Büchi Languages.

Michal Skrzypczak, Igor Walukiewicz

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Unambiguous Büchi Is Weak.

Henryk Michalewski, Michal Skrzypczak

Proceedings of the Developments in Language Theory - 20th International Conference, 2016

2015

On the Weak Index Problem for Game Automata.

Alessandro Facchini, Filip Murlak, Michal Skrzypczak

Proceedings of the Logic, Language, Information, and Computation, 2015

Irregular Behaviours for Probabilistic Automata.

Nathanaël Fijalkow, Michal Skrzypczak

Proceedings of the Reachability Problems - 9th International Workshop, 2015

On Determinisation of Good-for-Games Automata.

Denis Kuperberg, Michal Skrzypczak

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Trading Bounds for Memory in Games with Counters.

Nathanaël Fijalkow, Florian Horn, Denis Kuperberg, Michal Skrzypczak

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

On the topological complexity of ω-languages of non-deterministic Petri nets.

Olivier Finkel, Michal Skrzypczak

Inf. Process. Lett., 2014

Separation Property for wB- and wS-regular Languages.

Michal Skrzypczak

Log. Methods Comput. Sci., 2014

On the Topological Complexity of omega-Languages of Non-Deterministic Petri Nets.

Olivier Finkel, Michal Skrzypczak

CoRR, 2014

Measure Properties of Game Tree Languages.

Tomasz Gogacz, Henryk Michalewski, Matteo Mio, Michal Skrzypczak

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

On the Decidability of MSO+U on Infinite Trees.

Mikolaj Bojanczyk, Tomasz Gogacz, Henryk Michalewski, Michal Skrzypczak

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Topological extension of parity automata.

Michal Skrzypczak

Inf. Comput., 2013

Rabin-Mostowski Index Problem: A Step beyond Deterministic Automata.

Alessandro Facchini, Filip Murlak, Michal Skrzypczak

Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

Nondeterminism in the Presence of a Diverse or Unknown Future.

Udi Boker, Denis Kuperberg, Orna Kupferman, Michal Skrzypczak

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Unambiguity and uniformization problems on infinite trees.

Marcin Bilkowski, Michal Skrzypczak

Proceedings of the Computer Science Logic 2013 (CSL 2013), 2013

2012

The Topological Complexity of MSO+U and Related Automata Models.

Szczepan Hummel, Michal Skrzypczak

Fundam. Informaticae, 2012

2011

Equational theories of profinite structures

Michal Skrzypczak

CoRR, 2011

2010

On the Borel Complexity of MSO Definable Sets of Branches.

Mikolaj Bojanczyk, Damian Niwinski, Alexander Rabinovich, Adam Radziwonczyk-Syta, Michal Skrzypczak

Fundam. Informaticae, 2010

On the Topological Complexity of MSO+U and Related Automata Models.

Szczepan Hummel, Michal Skrzypczak, Szymon Torunczyk

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010