2017/08/22 by Laurette Marais, Lynette van Zijl
Computer Science · #cs.FL
paper · pdf · doi:10.4204/eptcs.252.16
published as EPTCS 252, 2017, pp. 157-169 · In Proceedings AFL 2017, arXiv:1708.06226
arxiv created 2017/08/22 · arxiv updated 2017/08/23
Previously, self-verifying symmetric difference automata were defined and a tight bound of 2n-1-1 was shown for state complexity in the unary case. We now consider the non-unary case and show that, for every n at least 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. Also, 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.