Decimations of languages and state complexity

Abstract: Let the words of a language be arranged in increasing radix order: . We consider transformations that extract terms from in an arithmetic progression. For example, two such transformations are and . Lecomte and Rigo observed that if is regular, then so are , , and analogous transformations of . We find good upper and lower bounds on the state complexity of this transformation. We also give an example of a context-free language such that is not context-free. [Copyright &y& Elsevier]