@InProceedings{10.1007/978-3-319-04921-2_35, author="Kaloci\'nski, Dariusz", editor="Dediu, Adrian-Horia and Mart{\'i}n-Vide, Carlos and Sierra-Rodr{\'i}guez, Jos{\'e}-Luis and Truthe, Bianca", title="On Computability and Learnability of the Pumping Lemma Function", booktitle="Language and Automata Theory and Applications", year="2014", publisher="Springer International Publishing", address="Cham", pages="433--440", abstract="On the basis of the well known pumping lemma for regular languages we define such a partial function f: {\$}{\{}{\backslash}mbox{\{}I{\backslash}!N{\}}{\}} {\backslash}rightarrow{\{}{\backslash}mbox{\{}I{\backslash}!N{\}}{\}}{\$} that for every e it yields the least pumping constant for the language W e . We ask whether f is computable. Not surprisingly f turns out to be non-computable. Then we check whether f is algorithmically learnable. This is also proved not to be the case. Further we investigate how powerful oracle is necessary to actually learn f. We prove that f is learnable in 0{\textasciiacutex}. We also prove some facts relating f to arithmetical hierarchy.", isbn="978-3-319-04921-2" }