ResearchSpace

Descriptional complexity of non-unary self-verifying symmetric difference automata

Show simple item record

dc.contributor.author Marais, Laurette
dc.contributor.author Van Zijl, L
dc.date.accessioned 2017-11-28T11:51:37Z
dc.date.available 2017-11-28T11:51:37Z
dc.date.issued 2017-09
dc.identifier.citation Marais, 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, Hungary en_US
dc.identifier.issn 2075-2180
dc.identifier.uri DOI: 10.4204/EPTCS.252.16
dc.identifier.uri https://arato.inf.unideb.hu/konferencia/afl2017/
dc.identifier.uri https://arato.inf.unideb.hu/konferencia/afl2017/ProceedingsAFL2017.pdf
dc.identifier.uri https://arxiv.org/abs/1708.06466
dc.identifier.uri http://hdl.handle.net/10204/9819
dc.description Paper presented at AFL 2017: 15th International Conference on Automata and Formal Languages, 4-6 September 2017, Debrecen, Hungary en_US
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.publisher Open Publishing Association en_US
dc.relation.ispartofseries Worklist;19703
dc.subject Automata en_US
dc.subject Formal languages en_US
dc.title Descriptional complexity of non-unary self-verifying symmetric difference automata en_US
dc.type Conference Presentation en_US
dc.identifier.apacitation Marais, L., & Van Zijl, L. (2017). Descriptional complexity of non-unary self-verifying symmetric difference automata. Open Publishing Association. http://hdl.handle.net/10204/9819 en_ZA
dc.identifier.chicagocitation Marais, Laurette, and L Van Zijl. "Descriptional complexity of non-unary self-verifying symmetric difference automata." (2017): http://hdl.handle.net/10204/9819 en_ZA
dc.identifier.vancouvercitation Marais L, Van Zijl L, Descriptional complexity of non-unary self-verifying symmetric difference automata; Open Publishing Association; 2017. http://hdl.handle.net/10204/9819 . en_ZA
dc.identifier.ris 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 - en_ZA


Files in this item

Thumbnail
Name: Marais_19703_2017.pdf
Size: 302.7Kb
Format: PDF
Description: Conference paper
View/Open

This item appears in the following Collection(s)

Show simple item record