NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS
Daniel Goč, Alexandros Palioudakis, Kai Salomaa · International Journal of Foundations of Computer Science · 2014
The language [Formula: see text] consists of first halfs of strings in L. Many other variants of a proportional removal operation have been considered in the literature and a characterization of removal operations that preserve regularity is known. We consider the nondeterministic state complexity of the operation [Formula: see text] and, more generally, of polynomial removals as defined by Domaratzki (J. Automata, Languages and Combinatorics 7(4), 2002). We give an O(n2) upper bound for the nondeterministic state complexity of polynomial removals and a matching lower bound in cases where the polynomial is a sum of a monomial and a constant, or when the polynomial has rational roots.