ResearchSpace

State complexity of unary SV-XNFA with different acceptance conditions

Show simple item record

dc.contributor.author Marais, Laurette
dc.contributor.author Van Zijl, Lynette
dc.date.accessioned 2018-07-10T08:07:10Z
dc.date.available 2018-07-10T08:07:10Z
dc.date.issued 2017-07
dc.identifier.citation Marais, 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-261 en_US
dc.identifier.isbn 978-3-319-60252-3
dc.identifier.uri https://link.springer.com/book/10.1007/978-3-319-60252-3
dc.identifier.uri https://link.springer.com/chapter/10.1007/978-3-319-60252-3_20
dc.identifier.uri doi.org/10.1007/978-3-319-60252-3_20
dc.identifier.uri http://hdl.handle.net/10204/10297
dc.description © 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. en_US
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.publisher Springer en_US
dc.relation.ispartofseries Worklist;19525
dc.subject Symmetric difference automata en_US
dc.subject Formal systems en_US
dc.title State complexity of unary SV-XNFA with different acceptance conditions en_US
dc.type Conference Presentation en_US
dc.identifier.apacitation Marais, L., & Van Zijl, L. (2017). State complexity of unary SV-XNFA with different acceptance conditions. Springer. http://hdl.handle.net/10204/10297 en_ZA
dc.identifier.chicagocitation Marais, Laurette, and Lynette Van Zijl. "State complexity of unary SV-XNFA with different acceptance conditions." (2017): http://hdl.handle.net/10204/10297 en_ZA
dc.identifier.vancouvercitation Marais L, Van Zijl L, State complexity of unary SV-XNFA with different acceptance conditions; Springer; 2017. http://hdl.handle.net/10204/10297 . en_ZA
dc.identifier.ris 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 - en_ZA


Files in this item

Thumbnail
Name: Marais_19525_2017.pdf
Size: 289.5Kb
Format: PDF
Description: Conference paper
View/Open

This item appears in the following Collection(s)

Show simple item record