Descriptional complexity of non-unary self-verifying symmetric difference automata

Abstract

Unary self-verifying symmetric difference automata have a known tight bound of 2n-1-1 for their state complexity. We now consider the non-unary case and show that, for every n=2, there is a regular language Ln accepted by a non-unary self-verifying symmetric difference nondeterministic automaton with n states, such that its equivalent minimal deterministic finite automaton has 2n-1 states. Furthermore, given any SV-XNFA with n states, it is possible, up to isomorphism, to find at most another |GL(n,Z2)|-1 equivalent SV-XNFA. Finally, we show that for a certain set of non-unary SV-XNFA, 2n-1 is a tight bound on the state complexity.