Algorithms and fine-grained complexity for nondeterministic and symmetric difference automata
For researchers in automata theory and fine-grained complexity, this work improves polynomial-time bounds for basic decision problems on XNFA, with implications for weighted automata.
The paper studies the fine-grained complexity of acceptance, emptiness, and equivalence problems for symmetric difference automata (XNFA). It provides faster algorithms for these problems under polynomial ambiguity and bounded ambiguity assumptions, and extends results to weighted automata over other semirings and fields.
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 weighted automata over the two-element field. We study the fine-grained complexity of the basic decision problems for XNFA: acceptance, emptiness, and equivalence, aiming to optimise the degree of the polynomial in their running-time bounds. Under the assumption of polynomial ambiguity, we provide a randomised reduction of NFA acceptance to XNFA acceptance. For automata of bounded ambiguity (e.g., unambiguous automata), we show that acceptance for both NFA and XNFA can be decided faster than in the general case. Without ambiguity assumptions, we give faster algorithms for the verification of suitable certificates for (non)emptiness and (non)equivalence of XNFA. Several of our results extend to weighted automata over other semirings and fields.