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…
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…
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 elap…