{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:23:32Z","timestamp":1770963812182,"version":"3.50.1"},"reference-count":17,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>We investigate the computational complexity of the Pumping-Problem, that is, for a given finite automaton\u00a0A and a value\u00a0p, to decide whether the language\u00a0[Formula: see text] satisfies a previously fixed pumping lemma w.r.t.\u00a0the value\u00a0p. Here we concentrate on two different pumping lemmata from the literature. It turns out that this problem is intractable, namely, it is already coNP -complete, even for deterministic finite automata (DFAs), and it becomes PSPACE -complete for nondeterministic finite state devices (NFAs), for at least one of the considered pumping lemmata. In addition, we show that the minimal pumping constant for the considered pumping lemmata cannot be approximated within a factor of\u00a0[Formula: see text] with [Formula: see text], for a given n-state NFA, unless the Exponential Time Hypothesis (ETH) fails.<\/jats:p>","DOI":"10.1142\/s0129054125410084","type":"journal-article","created":{"date-parts":[[2025,9,15]],"date-time":"2025-09-15T10:45:31Z","timestamp":1757933131000},"page":"193-213","source":"Crossref","is-referenced-by-count":0,"title":["The Pumping Lemma for Regular Languages is Hard"],"prefix":"10.1142","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1953-3697","authenticated-orcid":false,"given":"Hermann","family":"Gruber","sequence":"first","affiliation":[{"name":"Planerio GmbH, Theresienh\u00f6he\u00a011A, 80538 M\u00fcnchen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4224-4014","authenticated-orcid":false,"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstr.\u00a02, 35392 Giessen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1008-4642","authenticated-orcid":false,"given":"Christian","family":"Rauch","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, University of Kassel, 34121 Kassel, Germany"}]}],"member":"219","published-online":{"date-parts":[[2025,9,15]]},"reference":[{"key":"S0129054125410084BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322334"},{"key":"S0129054125410084BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"S0129054125410084BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"S0129054125410084BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-022-00431-3"},{"key":"S0129054125410084BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00095-6"},{"key":"S0129054125410084BIB006","volume-title":"Introduction to Formal Language Theory","author":"Harrison M. A.","year":"1978"},{"key":"S0129054125410084BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-34326-1_5"},{"key":"S0129054125410084BIB008","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804030"},{"key":"S0129054125410084BIB009","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"S0129054125410084BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/990524.990528"},{"key":"S0129054125410084BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1844-9"},{"key":"S0129054125410084BIB012","first-page":"34","volume":"17","author":"Nijholt A.","year":"1982","journal-title":"Bull. EATCS"},{"key":"S0129054125410084BIB013","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994"},{"key":"S0129054125410084BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023844"},{"key":"S0129054125410084BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90023-1"},{"key":"S0129054125410084BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"S0129054125410084BIB017","first-page":"1","volume-title":"Proceedings of the 5th Symposium on Theory of Computing","author":"Stockmeyer L. J.","year":"1973"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054125410084","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:37:01Z","timestamp":1770961021000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054125410084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,15]]},"references-count":17,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1142\/S0129054125410084"],"URL":"https:\/\/doi.org\/10.1142\/s0129054125410084","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,15]]}}}