Marais, LauretteVan Zijl, L2022-11-062022-11-062022-05Marais, L. & Van Zijl, L. 2022. Descriptional complexity of non-unary self-verifying symmetric difference automata. <i>International Journal of Foundations of Computer Science, 33(3/4).</i> http://hdl.handle.net/10204/125150129-0541https://doi.org/10.1142/S0129054122410076http://hdl.handle.net/10204/12515Unary 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.FulltextenDescriptional complexitySymmetric difference automataSelf-verifying automataArticleMarais, L., & Van Zijl, L. (2022). Descriptional complexity of non-unary self-verifying symmetric difference automata. <i>International Journal of Foundations of Computer Science, 33(3/4)</i>, http://hdl.handle.net/10204/12515Marais, Laurette, and L Van Zijl "Descriptional complexity of non-unary self-verifying symmetric difference automata." <i>International Journal of Foundations of Computer Science, 33(3/4)</i> (2022) http://hdl.handle.net/10204/12515Marais L, Van Zijl L. Descriptional complexity of non-unary self-verifying symmetric difference automata. International Journal of Foundations of Computer Science, 33(3/4). 2022; http://hdl.handle.net/10204/12515.TY - Article AU - Marais, Laurette AU - Van Zijl, L AB - 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. DA - 2022-05 DB - ResearchSpace DP - CSIR J1 - International Journal of Foundations of Computer Science, 33(3/4) KW - Descriptional complexity KW - Symmetric difference automata KW - Self-verifying automata LK - https://researchspace.csir.co.za PY - 2022 SM - 0129-0541 T1 - Descriptional complexity of non-unary self-verifying symmetric difference automata TI - Descriptional complexity of non-unary self-verifying symmetric difference automata UR - http://hdl.handle.net/10204/12515 ER -25965