6 citations · 15 across the 7 of their papers we have counts for
12 papers
Generalised Quantifiers Based on Rabin-Mostowski Index
Denis Kuperberg, Damian Niwiński, Paweł Parys +1
In this work we introduce new generalised quantifiers which allow us to express the Rabin-Mostowski index of automata. Our main results study expressive power and decidability of t…
Tree algebras and bisimulation-invariant MSO on finite graphs
Thomas Colcombet, Amina Doumane, Denis Kuperberg
We establish that the bisimulation invariant fragment of MSO over finite transition systems is expressively equivalent over finite transition systems to modal mu-calculus, a questi…
Positive First-order Logic on Words and Graphs
Denis Kuperberg
We study FO+, a fragment of first-order logic on finite words, where monadic predicates can only appear positively. We show that there is an FO-definable language that is monotone…
Positive first-order logic on words
Denis Kuperberg
We study FO+, a fragment of first-order logic on finite words, where monadic predicates can only appear positively. We show that there is a FO-definable language that is monotone i…
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…
Bouncing threads for infinitary and circular proofs
David Baelde, Amina Doumane, Denis Kuperberg +1
We generalize the validity criterion for the infinitary proof system of the multiplicative additive linear logic with fixed points. Our criterion is designed to take into account a…
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…
Regular resynchronizability of origin transducers is undecidable
Denis Kuperberg, Jan Martens
We study the relation of containment up to unknown regular resynchronization between two-way non-deterministic transducers. We show that it constitutes a preorder, and that the cor…
Computing the Width of Non-deterministic Automata
Denis Kuperberg, Anirban Majumdar
We introduce a measure called width, quantifying the amount of nondeterminism in automata. Width generalises the notion of good-for-games (GFG) automata, that correspond to NFAs of…
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…
Soundness in negotiations
Javier Esparza, Denis Kuperberg, Anca Muscholl +1
Negotiations are a formalism for describing multiparty distributed cooperation. Alternatively, they can be seen as a model of concurrency with synchronized choice as communication…
Linear Temporal Logic for Regular Cost Functions
Denis Kuperberg
Regular cost functions have been introduced recently as an extension to the notion of regular languages with counting capabilities, which retains strong closure, equivalence, and d…