3 papers
cs.FL2026
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…
cs.LO2026
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…
cs.FL2026
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…