The state complexity of language operations on XNFA-succinct unary regular languages

Given two unary languages accepted by symmetric difference non-deterministic finite automata, we establish bounds on the state complexity of their union, intersection, relative complement and symmetric difference. For languages L 1 and L 2 accepted by minimal symmetric difference nondeterministic finite automata of size m and n respectively, we show that the state complexity of their union, intersection and relative complement has an upper bound of (2 m - 1)(2 n - 1).