Pumping lemmas are among the most important results in the field of formal language theory. They provide necessary – and sometimes sufficient – conditions for a language to belong to a given family of languages. A. Nijholt compiled an annotated bibliography of variants for regular and context-free languages in 1982. Until recently, little was known about the descriptional and computational complexity of problems related to the pumping lemmas. This changed with J. Dassow and I. Jecker’s 2022 work on the operational complexity of minimal pumping constants.
This talk provides an overview of recent findings concerning the descriptional and computational complexity of minimal pumping constants. The focus is on the relationships between the constants induced by different pumping lemmas and other classical measures in automata theory. Moreover, the computational complexity of the pumping problem, i.e., determining the minimal pumping constant of a language given by a finite automaton, is also discussed, including recent results. Most of the work was done with H. Gruber (Planerio GmbH) and C. Rauch (Universität Kassel).