2 citations · 5 across the 3 of their papers we have counts for
13 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…