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 Ln=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.
Reference:
Marais, L., and van Zijl, L. 2016. Unary Self-verifying Symmetric Difference Automata. In: Câmpeanu, C., Manea, F., Shallit, J. (eds) Descriptional Complexity of Formal Systems. DCFS 2016. Lecture Notes in Computer Science, vol 9777. Springer, Cham
Marais, L., & Van Zijl, L. (2016). Unary self-verifying symmetric difference automata. Springer Nature. http://hdl.handle.net/10204/9579
Marais, Laurette, and L Van Zijl. "Unary self-verifying symmetric difference automata." (2016): http://hdl.handle.net/10204/9579
18th International Workshop on Descriptional Complexity of Formal Systems, 5 - 8 July 2016, Bucharest, Romania. Due to copyright restrictions, the attached PDF file only contains the abstract of the full text item. For access to the full text item, please consult the publisher's website
