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.FL2026
Intersecting Dense Automata
Dmitry Chistikov, Neha Rino
We observe that the classical Cartesian product construction for the intersection of (languages of) nondeterministic finite automata (NFA) is non-optimal in the worst case, if the…
cs.FL2024
The Tractability Border of Reachability in Simple Vector Addition Systems with States
Dmitry Chistikov, Wojciech CzerwiÅski, Filip Mazowiecki +3
Vector Addition Systems with States (VASS), equivalent to Petri nets, are a well-established model of concurrency. The central algorithmic challenge in VASS is the reachability pro…