State Complexity of Unary SV-XNFA with Different Acceptance Conditions - Descriptional Complexity of Formal Systems (DCFS 2017)
Conference Papers Year : 2017

State Complexity of Unary SV-XNFA with Different Acceptance Conditions

Abstract

Unary self-verifying symmetric difference automata were introduced in [1], with an upper bound of $O(2^{n})$ and lower bound of $2^{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^{n-1}-1$ for state complexity for both interpretations of acceptance.
Fichier principal
Vignette du fichier
440206_1_En_20_Chapter.pdf (281.37 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-01657002 , version 1 (06-12-2017)

Licence

Identifiers

Cite

Laurette Marais, Lynette Van Zijl. State Complexity of Unary SV-XNFA with Different Acceptance Conditions. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.250-261, ⟨10.1007/978-3-319-60252-3_20⟩. ⟨hal-01657002⟩
103 View
95 Download

Altmetric

Share

More