2017/11/10 by Michael Raskin, Raskin, Michael · 2 citations
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.CC #cs.FL
paper · pdf · doi:10.48550/arxiv.1711.03993
arxiv created 2018/02/14 · arxiv updated 2018/02/15
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.