State Complexity of Unary SV-XNFA with Different Acceptance Conditions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

State Complexity of Unary SV-XNFA with Different Acceptance Conditions

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Licence

Paternité

Identifiants

Citer

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⟩
56 Consultations
75 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More