Marais, LauretteVan Zijl, L2017-11-282017-11-282017-09Marais, L. and Van Zijl, L. 2017. Descriptional complexity of non-unary self-verifying symmetric difference automata. AFL 2017 15th International Conference on Automata and Formal Languages, 4-6 September 2017, Debrecen, Hungary2075-2180DOI: 10.4204/EPTCS.252.16https://arato.inf.unideb.hu/konferencia/afl2017/https://arato.inf.unideb.hu/konferencia/afl2017/ProceedingsAFL2017.pdfhttps://arxiv.org/abs/1708.06466http://hdl.handle.net/10204/9819Paper presented at AFL 2017: 15th International Conference on Automata and Formal Languages, 4-6 September 2017, Debrecen, HungaryPreviously, self-verifying symmetric difference automata were defined and a tight bound of 2^n-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 L_n accepted by a non-unary self-verifying symmetric difference nondeterministic automaton with n states, such that its equivalent minimal deterministic finite automaton has 2^n-1 states. Also, given any SV-XNFA with n states, it is possible, up to isomorphism, to find at most another |GL(n,Z_2)|-1 equivalent SV-XNFA.enAutomataFormal languagesConference PresentationMarais, L., & Van Zijl, L. (2017). Descriptional complexity of non-unary self-verifying symmetric difference automata. Open Publishing Association. http://hdl.handle.net/10204/9819Marais, Laurette, and L Van Zijl. "Descriptional complexity of non-unary self-verifying symmetric difference automata." (2017): http://hdl.handle.net/10204/9819Marais L, Van Zijl L, Descriptional complexity of non-unary self-verifying symmetric difference automata; Open Publishing Association; 2017. http://hdl.handle.net/10204/9819 .TY - Conference Presentation AU - Marais, Laurette AU - Van Zijl, L AB - Previously, self-verifying symmetric difference automata were defined and a tight bound of 2^n-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 L_n accepted by a non-unary self-verifying symmetric difference nondeterministic automaton with n states, such that its equivalent minimal deterministic finite automaton has 2^n-1 states. Also, given any SV-XNFA with n states, it is possible, up to isomorphism, to find at most another |GL(n,Z_2)|-1 equivalent SV-XNFA. DA - 2017-09 DB - ResearchSpace DP - CSIR KW - Automata KW - Formal languages LK - https://researchspace.csir.co.za PY - 2017 SM - 2075-2180 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/9819 ER -