乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T04:18:32Z","timestamp":1729916312705,"version":"3.28.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T00:00:00Z","timestamp":1712275200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T00:00:00Z","timestamp":1712275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,10]]},"abstract":"Abstract<\/jats:title>A pumping lemma for a class of languages

$$\\varvec{\\mathcal {C}}$$<\/jats:tex-math>\n \n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is often used to show particular languages are not in

$$\\varvec{\\mathcal {C}}$$<\/jats:tex-math>\n \n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In contrast, we show that a pumping lemma for a class of languages

$$\\varvec{\\mathcal {C}}$$<\/jats:tex-math>\n \n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be used to study the computational complexity of the predicate \u201c

$$\\in \\varvec{\\mathcal {C}}$$<\/jats:tex-math>\n \n \u2208<\/mml:mo>\n \n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u201d via highly efficient many-one reductions. In this paper, we use extended regular expressions (EXREGs, introduced in C\u00e2mpeanu et al. (Int. J. Foundations Comput. Sci. 14<\/jats:bold>(6), 1007\u20131018, 2003)) as an example to illustrate the proof technique and establish the complexity of the predicate \u201cis an EXREG language\u201d for several classes of languages. Due to the efficiency of the reductions, both productiveness (a stronger form of non-recursive enumerability) and complexity results can be obtained simultaneously. For example, we show that the predicate \u201cis an EXREG language\u201d is productive (hence, not recursively enumerable) for context-free grammars, and is Co-NEXPTIME-hard for context-free grammars generating bounded languages. The proof technique is easy to use and requires only a few conditions. This suggests that for any class of languages

$$\\varvec{\\mathcal {C}}$$<\/jats:tex-math>\n \n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> having a pumping lemma, the language class comparison problems (e.g., does a given context-free grammar generate a language in

$$\\varvec{\\mathcal {C}}$$<\/jats:tex-math>\n \n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>?) are almost guaranteed to be hard. So, pumping lemmas sometimes could be \u201charmful\u201d when studying computational complexity results.<\/jats:p>","DOI":"10.1007\/s00224-024-10169-9","type":"journal-article","created":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T02:09:48Z","timestamp":1712282988000},"page":"1339-1352","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Pumping Lemmas Can be \u201cHarmful\u201d"],"prefix":"10.1007","volume":"68","author":[{"given":"Jingnan","family":"Xie","sequence":"first","affiliation":[]},{"given":"Harry B.","family":"Hunt III","sequence":"additional","affiliation":[]},{"given":"Richard E.","family":"Stearns","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,5]]},"reference":[{"issue":"6","key":"10169_CR1","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1142\/S012905410300214X","volume":"14","author":"C C\u00e2mpeanu","year":"2003","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Yu, S.: A formal study of practical regular expressions. Int. J. Foundations Comput. Sci. 14(6), 1007\u20131018 (2003). https:\/\/doi.org\/10.1142\/S012905410300214X","journal-title":"Int. J. Foundations Comput. Sci."},{"key":"10169_CR2","doi-asserted-by":"publisher","unstructured":"Aho, A.V.: Algorithms for finding patterns in strings. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science Vol A: Algorithms and Complexity, pp. 255\u2013300. Elsevier, Amsterdam (1990). https:\/\/doi.org\/10.1016\/B978-0-444-88071-0.50010-2","DOI":"10.1016\/B978-0-444-88071-0.50010-2"},{"issue":"1","key":"10169_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00236-002-0099-y","volume":"39","author":"G Della Penna","year":"2003","unstructured":"Della Penna, G., Intrigila, B., Tronci, E., Venturini Zilli, M.: Synchronized regular expressions. Acta Informatica. 39(1), 31\u201370 (2003). https:\/\/doi.org\/10.1007\/s00236-002-0099-y","journal-title":"Acta Informatica."},{"key":"10169_CR4","doi-asserted-by":"publisher","unstructured":"Carle, B., Narendran, P.: On extended regular expressions. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) Language and Automata Theory and Applications. LATA 2009. Lecture Notes in Computer Science, vol. 5457, pp. 279\u2013289. Springer, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00982-2_24","DOI":"10.1007\/978-3-642-00982-2_24"},{"issue":"3","key":"10169_CR5","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/0022-5193(68)90079-9","volume":"18","author":"A Lindenmayer","year":"1968","unstructured":"Lindenmayer, A.: Mathematical models for cellular interactions in development i. filaments with one-sided inputs. J. Theoretical Biology. 18(3), 280\u2013299 (1968)","journal-title":"J. Theoretical Biology."},{"key":"10169_CR6","doi-asserted-by":"crossref","unstructured":"Kari, L., Rozenberg, G., Salomaa, A.: In: Rozenberg, G., Salomaa, A. (eds.) L Systems, pp. 253\u2013328. Springer, Berlin, Heidelberg (1997)","DOI":"10.1007\/978-3-642-59136-5_5"},{"key":"10169_CR7","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1016\/j.jalgebra.2022.11.031","volume":"619","author":"A Levine","year":"2023","unstructured":"Levine, A.: Edt0l solutions to equations in group extensions. J. Algebra. 619, 860\u2013899 (2023). https:\/\/doi.org\/10.1016\/j.jalgebra.2022.11.031","journal-title":"J. Algebra."},{"key":"10169_CR8","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/j.jalgebra.2023.04.020","volume":"630","author":"A Duncan","year":"2023","unstructured":"Duncan, A., Evetts, A., Holt, D.F., Rees, S.: Using edt0l systems to solve some equations in the solvable baumslag-solitar groups. J. Algebra. 630, 434\u2013456 (2023). https:\/\/doi.org\/10.1016\/j.jalgebra.2023.04.020","journal-title":"J. Algebra."},{"key":"10169_CR9","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.ijar.2021.12.002","volume":"142","author":"M Ghorani","year":"2022","unstructured":"Ghorani, M., Garhwal, S., Moghari, S.: Lattice-valued tree pushdown automata: pumping lemma and closure properties. Int. J. Approximate Reasoning. 142, 301\u2013323 (2022). https:\/\/doi.org\/10.1016\/j.ijar.2021.12.002","journal-title":"Int. J. Approximate Reasoning."},{"key":"10169_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s11047-019-09771-5","volume":"20","author":"JC Lucero","year":"2019","unstructured":"Lucero, J.C.: Pumping lemmas for classes of languages generated by folding systems. Natural Comput. 20, 321\u2013327 (2019). https:\/\/doi.org\/10.1007\/s11047-019-09771-5","journal-title":"Natural Comput."},{"key":"10169_CR11","doi-asserted-by":"publisher","unstructured":"Chattopadhyay, A., Mazowiecki, F., Muscholl, A., Riveros, C.: Pumping lemmas for weighted automata. Logical Methods Comput. Sci. 17(3) (2021). https:\/\/doi.org\/10.46298\/lmcs-17(3:7)2021","DOI":"10.46298\/lmcs-17(3:7)2021"},{"volume-title":"Introduction to automata theory, languages, and computation","year":"1979","author":"JE Hopcroft","key":"10169_CR12","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison-Wesley, Reading, MA (1979)"},{"volume-title":"Theory of recursive functions and effective computability","year":"1987","author":"H Rogers Jr","key":"10169_CR13","unstructured":"Rogers, H., Jr.: Theory of recursive functions and effective computability. MIT Press, Cambridge, MA, USA (1987)"},{"key":"10169_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively enumerable sets and degrees","author":"RI Soare","year":"1987","unstructured":"Soare, R.I.: Recursively enumerable sets and degrees. Springer, Berlin, Heidelberg (1987)"},{"issue":"3","key":"10169_CR15","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s00236-023-00439-3","volume":"60","author":"J Xie","year":"2023","unstructured":"Xie, J., Hunt, H.B., III.: On the undecidability and descriptional complexity of synchronized regular expressions. Acta Informatica. 60(3), 257\u2013278 (2023). https:\/\/doi.org\/10.1007\/s00236-023-00439-3","journal-title":"Acta Informatica."},{"issue":"1","key":"10169_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/0207007","volume":"7","author":"HB Hunt III","year":"1978","unstructured":"Hunt, H.B., III., Rosenkrantz, D.J.: Computational parallels between the regular and context-free languages. SIAM J. Comput. 7(1), 99\u2013114 (1978). https:\/\/doi.org\/10.1137\/0207007","journal-title":"SIAM J. Comput."},{"issue":"24","key":"10169_CR17","doi-asserted-by":"publisher","first-page":"2336","DOI":"10.1016\/j.tcs.2009.02.022","volume":"410","author":"C C\u00e2mpeanu","year":"2009","unstructured":"C\u00e2mpeanu, C., Santean, N.: On the intersection of regex languages with regular languages. Theoretical Comput. Sci. 410(24), 2336\u20132344 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.02.022","journal-title":"Theoretical Comput. Sci."},{"issue":"2","key":"10169_CR18","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/S0022-0000(76)80038-4","volume":"12","author":"HB Hunt III","year":"1976","unstructured":"Hunt, H.B., III., Rosenkrantz, D.J., Szymanski, T.G.: On the equivalence, containment, and covering problems for the regular and context-free languages. J. Comput. Syst. Sci. 12(2), 222\u2013268 (1976). https:\/\/doi.org\/10.1016\/S0022-0000(76)80038-4","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10169_CR19","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01744286","volume":"13","author":"ND Jones","year":"1979","unstructured":"Jones, N.D., Skyum, S.: Complexity of some problems concerning L systems. Math. Syst. Theory. 13(1), 29\u201343 (1979). https:\/\/doi.org\/10.1007\/BF01744286","journal-title":"Math. Syst. Theory."},{"key":"10169_CR20","doi-asserted-by":"publisher","unstructured":"Xie, J., Hunt, H.B., III., Stearns, R. E.: On the computational and descriptional complexity of multi-pattern languages. Available at SSRN (2023). https:\/\/doi.org\/10.2139\/ssrn.4493700","DOI":"10.2139\/ssrn.4493700"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10169-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10169-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10169-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T09:53:09Z","timestamp":1729849989000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10169-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,5]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10169"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10169-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,4,5]]},"assertion":[{"value":"29 February 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"The authors declare that they have no conflict of interest.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}