Unary Self-verifying Symmetric Difference Automata - Descriptional Complexity of Formal Systems (DCFS 2016)
Conference Papers Year : 2016

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.
Fichier principal
Vignette du fichier
416473_1_En_14_Chapter.pdf (287.4 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01633957 , version 1 (13-11-2017)

Licence

Identifiers

Cite

Laurette Marais, Lynette Van Zijl. Unary Self-verifying Symmetric Difference Automata. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.180-191, ⟨10.1007/978-3-319-41114-9_14⟩. ⟨hal-01633957⟩
57 View
126 Download

Altmetric

Share

More