{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T08:20:02Z","timestamp":1777105202867,"version":"3.51.4"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031661587","type":"print"},{"value":"9783031661594","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-66159-4_11","type":"book-chapter","created":{"date-parts":[[2024,7,26]],"date-time":"2024-07-26T09:01:34Z","timestamp":1721984494000},"page":"141-155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Pumping Lemma for Context-Free Languages is Undecidable"],"prefix":"10.1007","author":[{"given":"Hermann","family":"Gruber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Rauch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,27]]},"reference":[{"key":"11_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1102","DOI":"10.1007\/11523468_89","volume-title":"Automata, Languages and Programming","author":"R Alur","year":"2005","unstructured":"Alur, R., Kumar, V., Madhusudan, P., Viswanathan, M.: Congruences for visibly pushdown languages. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1102\u20131114. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11523468_89"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56(3), Art. 16 (2009)","DOI":"10.1145\/1516512.1516518"},{"key":"11_CR3","first-page":"143","volume":"14","author":"Y Bar-Hillel","year":"1961","unstructured":"Bar-Hillel, Y., Perles, M., Shamir, E.: On formal properties of simple phrase structure grammars. Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung 14, 143\u2013177 (1961)","journal-title":"Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung"},{"key":"11_CR4","doi-asserted-by":"publisher","unstructured":"Brauer, W.: Automatentheorie: Eine Einf\u00fchrung in die Theorie endlicher Automaten. Leitf\u00e4den und Monographien der Informatik, Teubner Stuttgart (1984). https:\/\/doi.org\/10.1007\/978-3-322-92151-2, (in German)","DOI":"10.1007\/978-3-322-92151-2"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00236-022-00431-3","volume":"59","author":"J Dassow","year":"2022","unstructured":"Dassow, J., Jecker, I.: Operational complexity and pumping lemmas. Acta Inform. 59, 337\u2013355 (2022). https:\/\/doi.org\/10.1007\/s00236-022-00431-3","journal-title":"Acta Inform."},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York (1966)","DOI":"10.1145\/321312.321318"},{"key":"11_CR7","doi-asserted-by":"publisher","unstructured":"Gruber, H., Holzer, M., Rauch, C.: The pumping lemma for regular languages is hard. In: Nagy, B. (eds.) Implementation and Application of Automata. CIAA 2023. LNCS, vol. 14151, pp. 128\u2013140. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-40247-0_9","DOI":"10.1007\/978-3-031-40247-0_9"},{"key":"11_CR8","unstructured":"Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Boston (1978)"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Hartmanis, J.: Context-free languages and Turing machine computations. In: Proceedings of Symposia in Applied Mathematics, vol. 19, pp. 42\u201351. American Mathematical Society, Providence, Rhode Island (1967)","DOI":"10.1090\/psapm\/019\/0235938"},{"key":"11_CR10","doi-asserted-by":"publisher","unstructured":"Holzer, M., Rauch, C.: On Jaffe\u2019s pumping lemma, revisited. In: Bordihn, H., Tran, N., Vaszil, G. (eds.) Descriptional Complexity of Formal Systems. DCFS 2023. LNCS, vol. 13918, pp. 65\u201378. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-34326-1_5","DOI":"10.1007\/978-3-031-34326-1_5"},{"key":"11_CR11","doi-asserted-by":"publisher","unstructured":"Holzer, M., Rauch, C.: On minimal pumping constants for regular languages. In: Gazdag, Z., Iv\u00e1n, S., Kov\u00e1sznai, G. (eds.) Proceedings of the $$16$$th International Conference on Automata and Formal Languages, pp. 127\u2013141. No.\u00a0386 in EPTCS, Eger, Hungary (2023). https:\/\/doi.org\/10.4204\/EPTCS.386.11","DOI":"10.4204\/EPTCS.386.11"},{"key":"11_CR12","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston (1979)"},{"issue":"3","key":"11_CR13","first-page":"193","volume":"12","author":"S Horv\u00e1th","year":"1978","unstructured":"Horv\u00e1th, S.: The family of languages satisfying Bar-Hillel\u2019s lemma. RAIRO-Informatique th\u00e9orique et Applications\/Theoretical Informatics and Applications 12(3), 193\u2013199 (1978)","journal-title":"RAIRO-Informatique th\u00e9orique et Applications\/Theoretical Informatics and Applications"},{"key":"11_CR14","doi-asserted-by":"publisher","unstructured":"Jaffe, J.: A necessary and sufficient pumping lemma for regular languages. SIGACT News 10(2), 48\u201349 (1978). https:\/\/doi.org\/10.1145\/990524.990528","DOI":"10.1145\/990524.990528"},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/978-3-319-04921-2_35","volume-title":"Language and Automata Theory and Applications","author":"D Kaloci\u0144ski","year":"2014","unstructured":"Kaloci\u0144ski, D.: On computability and learnability of the pumping lemma function. In: Dediu, A.-H., Mart\u00edn-Vide, C., Sierra-Rodr\u00edguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 433\u2013440. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-04921-2_35"},{"key":"11_CR16","doi-asserted-by":"publisher","unstructured":"Kozen, D.C.: Automata and Computability. Undergraduate Texts in Computer Science, Springer, New York (1997). https:\/\/doi.org\/10.1007\/978-1-4612-1844-9","DOI":"10.1007\/978-1-4612-1844-9"},{"key":"11_CR17","unstructured":"Lange, M., Lei\u00df, H.: To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. Inform. Didact. 8 (2009)"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114\u2013125 (1959). https:\/\/doi.org\/10.1147\/rd.32.0114","journal-title":"IBM J. Res. Dev."},{"key":"11_CR19","unstructured":"Rogers Jr, H.: Theory of Recursive Functions and Effective Computability. Higher Mathematics. McGraw-Hill, New York (1967)"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Sommerhalder, R.: Classes of languages proof against regular pumping. RAIRO-Informatique th\u00e9orique et Applications\/Theoretical Informatics and Applications 14(2), 169\u201318 (1980)","DOI":"10.1051\/ita\/1980140201691"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-66159-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T08:03:16Z","timestamp":1729324996000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-66159-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031661587","9783031661594"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-66159-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"27 July 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"G\u00f6ttingen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}