Descriptional complexity of ambiguity in symmetric difference NFAs

Simple item page
dc.contributor.authorvan Zijl L.
dc.contributor.authorGeldenhuys J.
dc.date.accessioned2011-10-13T16:58:35Z
dc.date.available2011-10-13T16:58:35Z
dc.date.issued2011
dc.description.abstractWe 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.
dc.description.versionArticle
dc.identifier.citationJournal of Universal Computer Science
dc.identifier.citation17
dc.identifier.citation6
dc.identifier.citationhttp://www.scopus.com/inward/record.url?eid=2-s2.0-79959953842&partnerID=40&md5=31bc862d34bb5df2984b9b8f146b0c57
dc.identifier.issn9486968
dc.identifier.urihttp://hdl.handle.net/10019.1/16775
dc.subjectAmbiguity
dc.subjectNondeterminism
dc.subjectSuccinctness
dc.titleDescriptional complexity of ambiguity in symmetric difference NFAs
dc.typeArticle
Files
Collections
Stellenbosch University - Scopus Publications