@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"
}