Descriptional complexity of ambiguity in symmetric difference NFAs

Date
2011
Authors
van Zijl L.
Geldenhuys J.
Journal Title
Journal ISSN
Volume Title
Publisher
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. © J.UCS.
Description
Keywords
Ambiguity, Nondeterminism, Succinctness
Citation
Journal of Universal Computer Science
17
6
http://www.scopus.com/inward/record.url?eid=2-s2.0-79959953842&partnerID=40&md5=31bc862d34bb5df2984b9b8f146b0c57
URI
http://hdl.handle.net/10019.1/16775
Collections
Stellenbosch University - Scopus Publications