Marais, LauretteVan Zijl, Lynette2018-07-102018-07-102017-07Marais, L. and Van Zijl, L. 2017. State complexity of unary SV-XNFA with different acceptance conditions. Proceedings of the 19th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems (DCFS) 2017, 3-5 July 2017, Milano, Italy, pp. 250-261978-3-319-60252-3https://link.springer.com/book/10.1007/978-3-319-60252-3https://link.springer.com/chapter/10.1007/978-3-319-60252-3_20doi.org/10.1007/978-3-319-60252-3_20http://hdl.handle.net/10204/10297© IFIP International Federation for Information Processing 2017. Due to copyright restrictions, the attached PDF file contains the accepted version of the published paper. For access to the published item, please consult the publisher's website.Unary self-verifying symmetric difference automata were introduced in [1], with an upper bound of O(2(supn) ) and lower bound of 2(sup n-1) -1 for state complexity. Implicit in the interpretation of self-verifying acceptance for the symmetric difference case was the assumption that no state could be both an accept state and a reject state. We present another interpretation of acceptance more aligned to the equivalence of symmetric difference automata to weighted automata over GF(2), where states that both accept and reject are allowed, and we give a tight bound of 2(sup n-1) -1 for state complexity for both interpretations of acceptance.enSymmetric difference automataFormal systemsConference PresentationMarais, L., & Van Zijl, L. (2017). State complexity of unary SV-XNFA with different acceptance conditions. Springer. http://hdl.handle.net/10204/10297Marais, Laurette, and Lynette Van Zijl. "State complexity of unary SV-XNFA with different acceptance conditions." (2017): http://hdl.handle.net/10204/10297Marais L, Van Zijl L, State complexity of unary SV-XNFA with different acceptance conditions; Springer; 2017. http://hdl.handle.net/10204/10297 .TY - Conference Presentation AU - Marais, Laurette AU - Van Zijl, Lynette AB - Unary self-verifying symmetric difference automata were introduced in [1], with an upper bound of O(2(supn) ) and lower bound of 2(sup n-1) -1 for state complexity. Implicit in the interpretation of self-verifying acceptance for the symmetric difference case was the assumption that no state could be both an accept state and a reject state. We present another interpretation of acceptance more aligned to the equivalence of symmetric difference automata to weighted automata over GF(2), where states that both accept and reject are allowed, and we give a tight bound of 2(sup n-1) -1 for state complexity for both interpretations of acceptance. DA - 2017-07 DB - ResearchSpace DP - CSIR KW - Symmetric difference automata KW - Formal systems LK - https://researchspace.csir.co.za PY - 2017 SM - 978-3-319-60252-3 T1 - State complexity of unary SV-XNFA with different acceptance conditions TI - State complexity of unary SV-XNFA with different acceptance conditions UR - http://hdl.handle.net/10204/10297 ER -