Complexity of exclusive nondeterministic finite automata
Martin Kutrib, Andreas Malcher, Matthias Wendlandt · Information and Computation · 2025
Exclusive nondeterministic finite automata (XNFA) are nondeterministic finite automata with an exclusive-or-like acceptance condition. An input is accepted if there is exactly one accepting path in its computation tree. If there are none or more than one accepting paths, the input is rejected. It turns out that, from a descriptional complexity point of view, XNFAs differ significantly from the known types of finite automata. In particular the state costs for the simulation of an XNFA by a DFA are states, while the costs for simulating an XNFA by an NFA are states. Both bounds are also shown to be tight. On the other hand, NFAs may have advantages in comparison to XNFAs. For the simulation of an NFA by an XNFA, a tight bound of states is given. Finally, we investigate the computational complexity of different decision problems for XNFAs and it turns out that emptiness, universality, inclusion, and equivalence are PSPACE -complete.