State Complexity of Proportional Removals

Abstract

We examine the state complexity of proportional removals such as $\frac{1}{2}(L)$. For $\frac{1}{2}(L)$, we show a bound which is tight in the case that $L$ is a unary language, and an nearly optimal bound for arbitrary languages. We also compute the average state complexity for $\frac{1}{2}(L)$ if $L$ is unary. We study other proportional removals and give bounds for certain reset automata.