Michal Skrzypczak

Orcid: 0000-0002-9647-4993

Affiliations:
  • University of Warsaw, Poland


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Positionality in Σ⁰₂ and a Completeness Result.
Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Uniformisation of Regular Relations in First-Order Logic with Two Variables.
Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

2023
Positionality in Σ_0^2 and a completeness result.
CoRR, 2023

The Probabilistic Rabin Tree Theorem.
CoRR, 2023

The Probabilistic Rabin Tree Theorem<sup>*</sup>.
Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science, 2023

Languages Given by Finite Automata over the Unary Alphabet.
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.
Inf. Comput., 2021

Preface.
Fundam. Informaticae, 2021

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

Unambiguity in Automata Theory (Dagstuhl Seminar 21452).
Dagstuhl Reports, 2021

On Guidable Index of Tree Automata.
Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Deterministic and Game Separability for Regular Languages of Infinite Trees.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

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

Regular Choice Functions and Uniformisations For countable Domains.
Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Uniformisations of Regular Relations Over Bi-Infinite Words.
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.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

On the Succinctness of Alternating Parity Good-For-Games Automata.
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.
Log. Methods Comput. Sci., 2019

Regular tree languages in low levels of the Wadge Hierarchy.
Log. Methods Comput. Sci., 2019

MSO+nabla is undecidable.
CoRR, 2019

Uniformisation Gives the Full Strength of Regular Languages.
Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

MSO+∇ is undecidable.
Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, 2019

2018
Monadic Second Order Logic with Measure and Category Quantifiers.
Log. Methods Comput. Sci., 2018

On the Strength of Unambiguous Tree Automata.
Int. J. Found. Comput. Sci., 2018

Büchi VASS Recognise ∑<sup>1</sup><sub>1</sub>-complete ω-languages.
Proceedings of the Reachability Problems - 12th International Conference, 2018

Unambiguous Languages Exhaust the Index Hierarchy.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
Measure properties of regular sets of trees.
Inf. Comput., 2017

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

A Characterisation of Pi^0_2 Regular Tree Languages.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

How Deterministic are Good-For-Games Automata?.
Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

Connecting Decidability and Complexity for MSO Logic.
Proceedings of the Developments in Language Theory - 21st International Conference, 2017

2016
Descriptive Set Theoretic Methods in Automata Theory - Decidability and Topological Complexity
Lecture Notes in Computer Science 9802, Springer, ISBN: 978-3-662-52947-8, 2016

Index Problems for Game Automata.
ACM Trans. Comput. Log., 2016

Regular Languages of Thin Trees.
Theory Comput. Syst., 2016

On the Complexity of Branching Games with Regular Conditions.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Deciding the Topological Complexity of Büchi Languages.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Unambiguous Büchi Is Weak.
Proceedings of the Developments in Language Theory - 20th International Conference, 2016

2015
On the Weak Index Problem for Game Automata.
Proceedings of the Logic, Language, Information, and Computation, 2015

Irregular Behaviours for Probabilistic Automata.
Proceedings of the Reachability Problems - 9th International Workshop, 2015

On Determinisation of Good-for-Games Automata.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Trading Bounds for Memory in Games with Counters.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
On the topological complexity of ω-languages of non-deterministic Petri nets.
Inf. Process. Lett., 2014

Separation Property for wB- and wS-regular Languages.
Log. Methods Comput. Sci., 2014

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

Measure Properties of Game Tree Languages.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

On the Decidability of MSO+U on Infinite Trees.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Topological extension of parity automata.
Inf. Comput., 2013

Rabin-Mostowski Index Problem: A Step beyond Deterministic Automata.
Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

Nondeterminism in the Presence of a Diverse or Unknown Future.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Unambiguity and uniformization problems on infinite trees.
Proceedings of the Computer Science Logic 2013 (CSL 2013), 2013

2012
The Topological Complexity of MSO+U and Related Automata Models.
Fundam. Informaticae, 2012

2011
Equational theories of profinite structures
CoRR, 2011

2010
On the Borel Complexity of MSO Definable Sets of Branches.
Fundam. Informaticae, 2010

On the Topological Complexity of MSO+U and Related Automata Models.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010


  Loading...