Unary Self-verifying Symmetric Difference Automata

Abstract : We investigate self-verifying nondeterministic finite automata, in the case of unary symmetric difference nondeterministic finite automata (SV-XNFA). We show that there is a family of languages $$\mathcal {L}_{n\ge 2}$$ which can always be represented non-trivially by unary SV-XNFA. We also consider the descriptional complexity of unary SV-XNFA, giving an upper and lower bound for state complexity.
Document type :
Conference papers
Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.180-191, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_14〉
Liste complète des métadonnées

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01633957
Contributor : Hal Ifip <>
Submitted on : Monday, November 13, 2017 - 3:32:56 PM
Last modification on : Monday, November 13, 2017 - 3:35:32 PM
Document(s) archivé(s) le : Wednesday, February 14, 2018 - 3:15:27 PM

File

416473_1_En_14_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Laurette Marais, Lynette Zijl. Unary Self-verifying Symmetric Difference Automata. Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.180-191, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_14〉. 〈hal-01633957〉

Share

Metrics

Record views

35