On Pumping Preserving Homomorphisms and the Complexity of the Pumping Problem

Abstract

This paper complements a recent inapproximability result for the minimal pumping constant w.r.t. a fixed regular pumping lemma for nondeterministic finite automata [H. Gruber and M. Holzer and C. Rauch. The Pumping Lemma for Regular Languages is Hard. CIAA 2023, pp. 128-140.], by showing the inapproximability of this problem even for deterministic finite automata, and at the same time proving stronger lower bound on the attainable approximation ratio, assuming the Exponential Time Hypothesis (ETH). To that end, we describe those homomorphisms that, in a precise sense, preserve the respective pumping arguments used in two different pumping lemmata. We show that, perhaps surprisingly, this concept coincides with the classic notion of star height preserving homomorphisms as studied by McNaughton, and by Hashiguchi and Honda in the 1970s. Also, we gain a complete understanding of the minimal pumping constant for bideterministic finite automata, which may be of independent interest.