6 citations · 18 across the 8 of their papers we have counts for
16 papers
Computing measures of weak-MSO definable sets of trees
Damian Niwiński, Marcin Przybyłko, Michał Skrzypczak
This work addresses the problem of computing measures of recognisable sets of infinite trees. An algorithm is provided to compute the probability measure of a tree language recogni…
Languages given by Finite Automata over the Unary Alphabet
Wojciech Czerwiński, Maciej Dębski, Tomasz Gogasz +5
This paper studies the complexity of operations on finite automata and the complexity of their decision problems when the alphabet is unary. Let denote the maximum of the numbe…
On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
Olivier Finkel, Michał Skrzypczak
We prove that -languages of (non-deterministic) Petri nets and -languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hie…
Deterministic and game separability for regular languages of infinite trees
Lorenzo Clemente, Michał Skrzypczak
We show that it is decidable whether two regular languages of infinite trees are separable by a deterministic language, resp., a game language. We consider two variants of separabi…
On the Succinctness of Alternating Parity Good-for-Games Automata
Udi Boker, Denis Kuperberg, Karoliina Lehtinen +1
We study alternating parity good-for-games (GFG) automata, i.e., alternating parity automata where both conjunctive and disjunctive choices can be resolved in an online manner, wit…
On Succinctness and Recognisability of Alternating Good-for-Games Automata
Udi Boker, Denis Kuperberg, Karoliina Lehtinen +1
We study alternating good-for-games (GFG) automata, i.e., alternating automata where both conjunctive and disjunctive choices can be resolved in an online manner, without knowledge…
MSO+nabla is undecidable
Mikołaj Bojańczyk, Edon Kelmendi, Michał Skrzypczak
This paper is about an extension of monadic second-order logic over the full binary tree, which has a quantifier saying ``almost surely a branch π \in {0, 1}^w satisfies a formula…
Regular tree languages in low levels of the Wadge Hierarchy
Mikołaj Bojańczyk, Filippo Cavallari, Thomas Place +1
In this article we provide effective characterisations of regular languages of infinite trees that belong to the low levels of the Wadge hierarchy. More precisely we prove decidabi…
Unambiguous languages exhaust the index hierarchy
Michał Skrzypczak
This work is a study of the expressive power of unambiguity in the case of automata over infinite trees. An automaton is called unambiguous if it has at most one accepting run on e…
How Deterministic are Good-For-Games Automata?
Udi Boker, Orna Kupferman, Michał Skrzypczak
In GFG automata, it is possible to resolve nondeterminism in a way that only depends on the past and still accepts all the words in the language. The motivation for GFG automata co…
Trading Bounds for Memory in Games with Counters
Nathanaël Fijalkow, Florian Horn, Denis Kuperberg +1
We study two-player games with counters, where the objective of the first player is that the counter values remain bounded. We investigate the existence of a trade-off between the…
Monadic Second Order Logic with Measure and Category Quantifiers
Matteo Mio, Michał Skrzypczak, Henryk Michalewski
We investigate the extension of Monadic Second Order logic, interpreted over infinite words and trees, with generalized "for almost all" quantifiers interpreted using the notions o…
The logical strength of Büchi's decidability theorem
Leszek Kołodziejczyk, Henryk Michalewski, Cécilia Pradic +1
We study the strength of axioms needed to prove various results related to automata on infinite words and Büchi's theorem on the decidability of the MSO theory of . We…
Index problems for game automata
Alessandro Facchini, Filip Murlak, Michał Skrzypczak
For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a non-deterministic, alternating, or weak…
On the Topological Complexity of omega-Languages of Non-Deterministic Petri Nets
Olivier Finkel, Michał Skrzypczak
We show that there are -complete languages of infinite words accepted by non-deterministic Petri nets with Büchi acceptance condition, or equivalently by Büchi blind counter…
Unambiguous Buchi is weak
Henryk Michalewski, Michał Skrzypczak
A non-deterministic automaton running on infinite trees is unambiguous if it has at most one accepting run on every tree. The class of languages recognisable by unambiguous tree au…