JUCS - Journal of Universal Computer Science 17(6): 874-890, doi: 10.3217/jucs-017-06-0874
Descriptional Complexity of Ambiguity in Symmetric Difference NFAs
expand article infoLynette van Zijl‡, Jaco Geldenhuys
‡ Stellenbosch University, Stellenbosch, South Africa

Corresponding author: Lynette van Zijl ( lvzijl@sun.ac.za )

© Lynette van Zijl, Jaco Geldenhuys.
This article is freely available under the J.UCS Open Content License.
Citation: van Zijl L, Geldenhuys J (2011) Descriptional Complexity of Ambiguity in Symmetric Difference NFAs. JUCS - Journal of Universal Computer Science 17(6): 874-890. https://doi.org/10.3217/jucs-017-06-0874
Open Access
Abstract
We investigate ambiguity for symmetric difference nondeterministic finite automata. We show the existence of unambiguous, finitely ambiguous, polynomially ambiguous and exponentially ambiguous symmetric difference nondeterministic finite automata. We show that, for each of these classes, there is a family of n-state nondeterministic finite automata such that the smallest equivalent deterministic finite automata have O(2n) states.
Keywords
nondeterminism, ambiguity, succinctness