Ambiguity of unary symmetric difference NFAs

Simple item page
dc.contributor.authorVan Der Merwe B.
dc.contributor.authorVan Zijl L.
dc.contributor.authorGeldenhuys J.
dc.date.accessioned2011-10-13T16:58:16Z
dc.date.available2011-10-13T16:58:16Z
dc.date.issued2011
dc.description.abstractOkhotin [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.
dc.description.versionConference Paper
dc.identifier.citationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.identifier.citation6916 LNCS
dc.identifier.citationhttp://www.scopus.com/inward/record.url?eid=2-s2.0-80052712345&partnerID=40&md5=ffce6395c4007c002202d824327a716a
dc.identifier.issn3029743
dc.identifier.other10.1007/978-3-642-23283-1_17
dc.identifier.urihttp://hdl.handle.net/10019.1/16667
dc.subjectambiguity
dc.subjectnondeterminism
dc.subjectambiguity
dc.subjectnondeterminism
dc.subjectNondeterministic finite automaton
dc.subjectNumber of state
dc.subjectSymmetric difference
dc.subjectCommerce
dc.subjectFinite automata
dc.titleAmbiguity of unary symmetric difference NFAs
dc.typeConference Paper
Files
Collections
Stellenbosch University - Scopus Publications