State complexity of deletion and bipolar deletion

Abstract

It is well known that the language obtained by deleting an arbitrary language from a regular language is regular. We give an upper bound for the state complexity of deleting an arbitrary language from a regular language and a matching lower bound. We show that the state complexity of deletion is $n \cdot 2^{n-1}$ (respectively, $(n + \frac{1}{2}) \cdot 2^n - 2$) when using complete (respectively, incomplete) deterministic finite automata. We show that the state complexity of bipolar deletion has an upper bound $n^n$ (respectively $(n+1)^n - 1$) when using complete (respectively, incomplete) deterministic finite automata. In both cases we give almost matching lower bounds.