State Complexity of Unary SV-XNFA with Different Acceptance Conditions
| Autor: | Laurette Marais, Lynette van Zijl |
|---|---|
| Přispěvatelé: | Stellenbosch University, Council for Scientific and Industrial Research [Pretoria] (CSIR), Giovanni Pighizzini, Cezar Câmpeanu, TC 1, WG 1.2 |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science 19th International Conference on Descriptional Complexity of Formal Systems (DCFS) 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⟩ Descriptional Complexity of Formal Systems ISBN: 9783319602516 DCFS |
| DOI: | 10.1007/978-3-319-60252-3_20⟩ |
| Popis: | Part 2: Contributed Papers; International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|