1 citations · 1 across the 4 of their papers we have counts for
4 papers
Algorithms and fine-grained complexity for nondeterministic and symmetric difference automata
Dmitry Chistikov, Radosław Piórkowski, Neha Rino +1
Symmetric difference automata (XNFA) are a variant of standard finite automata in which an input word is accepted iff the number of accepting runs is odd. Equivalently, these are w…
Scoped MSO, Register Automata, and Expressions: Equivalence over Data Words
Radosław Piórkowski
This paper establishes logical and expression-based characterizations for the class of languages recognized by nondeterministic register automata with guessing (NRA) over infinite…
One-clock synthesis problems
Sławomir Lasota, Mathieu Lehaut, Julie Parreaux +1
We study a generalisation of Büchi-Landweber games to the timed setting. The winning condition is specified by a non-deterministic timed automaton, and one of the players can elaps…
Universal quantification makes automatic structures hard to decide
Christoph Haase, Radoslaw Piórkowski
Automatic structures are first-order structures whose universe and relations can be represented as regular languages. It follows from the standard closure properties of regular lan…