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