On Pumping Problems for Unary Regular Languages
摘要
Recently, the descriptional and computational complexity of various pumping lemmata for general regular languages have been investigated in the literature. There it turned out that in almost all cases tight bounds on the operational complexity of minimal pumping constants for regular languages have been obtained. From the computational perspective it was shown that in most cases the question whether a certain value can serve as a pumping constant w.r.t. a fixed pumping lemma is computationally intractable. Whether similar results can be obtained for restricted regular languages, such as unary regular languages, was left open—a language is unary if the underlying alphabet is a singleton set. Here we fill this gap by considering in detail questions on various pumping lemmata for unary regular languages. While some of the results obtained are similar to those in the general case, we also find significant differences. The results presented here fit well with the previous results and give a mostly complete picture of the problems in question.