Title: A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton,
Abstract: Unambiguous non-deterministic finite automata have intermediate expressive
power and succinctness between deterministic and non-deterministic automata. It
has been conjectured that every unambiguous non-deterministic one-way finite
automaton (1UFA) recognizing some language L can be converted into a 1UFA
recognizing the complement of the original language L with polynomial increase
in the number of states. We disprove this conjecture by presenting a family of
1UFAs on a single-letter alphabet such that recognizing the complements of the
corresponding languages requires superpolynomial increase in the number of
states even for generic non-deterministic one-way finite automata. We also note
that both the languages and their complements can be recognized by sweeping
deterministic automata with a linear increase in the number of states.