Ambiguity of unary symmetric difference NFAs

Van Der Merwe B.; Van Zijl L.; Geldenhuys J.

Ambiguity of unary symmetric difference NFAs

Date

2011

Authors

Van Der Merwe B.

Van Zijl L.

Geldenhuys J.

Abstract

Okhotin [9] showed an exponential trade-off in the conversion from nondeterministic unary finite automata to unambiguous nondeterministic unary finite automata. In this paper, we consider the trade-off in the case of unary symmetric difference finite automata to finitely ambiguous unary symmetric difference finite automata. Surprisingly, the trade-off is linear in the number of states of the finite automaton. In particular, for every n-state unary nondeterministic symmetric difference finite automaton, there is an equivalent finitely ambiguous n-state unary symmetric difference nondeterministic finite automaton. We also note other relevant ambiguity issues in the unary case, such as the ambiguity of k-deterministic finite automata. © 2011 Springer-Verlag.

Keywords

ambiguity, nondeterminism, ambiguity, nondeterminism, Nondeterministic finite automaton, Number of state, Symmetric difference, Commerce, Finite automata

Citation

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
6916 LNCS
http://www.scopus.com/inward/record.url?eid=2-s2.0-80052712345&partnerID=40&md5=ffce6395c4007c002202d824327a716a