Go home now Header Background Image
Search
Submission Procedure
share: |
 
Follow us
 
 
 
 
Volume 17 / Issue 6

available in:   PDF (163 kB) PS (199 kB)
 
get:  
Similar Docs BibTeX   Write a comment
  
get:  
Links into Future
 
DOI:   10.3217/jucs-017-06-0874

 

Descriptional Complexity of Ambiguity in Symmetric Difference NFAs

Lynette van Zijl (Stellenbosch University, South Africa)

Jaco Geldenhuys (Stellenbosch University, South Africa)

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: ambiguity, nondeterminism, succinctness

Categories: F.1.1, F.1.2