16 citations · 188 across the 122 of their papers we have counts for
7 papers · 1 filter
Box-Reachability in Vector Addition Systems
Shaull Almagor, Itay Hasson, Michał Pilipczuk +1
We consider a variant of reachability in Vector Addition Systems (VAS) dubbed \emph{box reachability}, whereby a vector is box-reachable from in a VAS i…
Simple and tight complexity lower bounds for solving Rabin games
Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk +2
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time , where $k…
On Rational Recursive Sequences
Lorenzo Clemente, Maria Donten-Bury, Filip Mazowiecki +1
We study the class of rational recursive sequences (ratrec) over the rational numbers. A ratrec sequence is defined via a system of sequences using mutually recursive equations of…
On polynomial recursive sequences
Michaël Cadilhac, Filip Mazowiecki, Charles Paperman +2
We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the…
The monitoring problem for timed automata
Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk +2
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a…
Reachability for Bounded Branching VASS
Filip Mazowiecki, Michał Pilipczuk
In this paper we consider the reachability problem for bounded branching VASS. Bounded VASS are a variant of the classic VASS model where all values in all configurations are upper…
Shortest paths in one-counter systems
Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman +2
We show that any one-counter automaton with states, if its language is non-empty, accepts some word of length at most . This closes the gap between the previously known…