{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T21:30:32Z","timestamp":1769290232365,"version":"3.49.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:00:00Z","timestamp":1760140800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:00:00Z","timestamp":1760140800000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00224-025-10246-7","type":"journal-article","created":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:23:04Z","timestamp":1760192584000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Decision Problems Concerning L Systems"],"prefix":"10.1007","volume":"69","author":[{"given":"Jingnan","family":"Xie","sequence":"first","affiliation":[]},{"suffix":"III","given":"Harry B.","family":"Hunt","sequence":"additional","affiliation":[]},{"given":"Richard E.","family":"Stearns","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,10,11]]},"reference":[{"key":"10246_CR1","doi-asserted-by":"publisher","unstructured":"Lindenmayer, A.: Mathematical models for cellular interactions in development I. Filaments with one-sided inputs. Journal of Theoretical Biology 18(3), 280\u2013299 (1968). https:\/\/doi.org\/10.1016\/0022-5193(68)90079-9","DOI":"10.1016\/0022-5193(68)90079-9"},{"key":"10246_CR2","doi-asserted-by":"publisher","unstructured":"Bishop, A., Elder, M.: Bounded automata groups are co-et0l. In: Mart\u00edn-Vide, C., Okhotin, A., Shapira, D. (eds.) Language and Automata Theory and Applications, pp. 82\u201394. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-13435-8_6","DOI":"10.1007\/978-3-030-13435-8_6"},{"key":"10246_CR3","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":"10246_CR4","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":"10246_CR5","doi-asserted-by":"publisher","unstructured":"Rozenberg, G., Salomaa, A.: The Mathematical Theory of L Systems. In: Tou, J.T. (ed.) Advances in Information Systems Science: Volume 6, pp. 161\u2013206. Springer, Boston, MA (1976). https:\/\/doi.org\/10.1007\/978-1-4615-8249-6_4","DOI":"10.1007\/978-1-4615-8249-6_4"},{"key":"10246_CR6","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-642-59136-5_5","volume-title":"Handbook of Formal Languages: Volume 1 Word, Language, Grammar","author":"L Kari","year":"1997","unstructured":"Kari, L., Rozenberg, G., Salomaa, A.: L systems. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages: Volume 1 Word, Language, Grammar, pp. 253\u2013328. Springer, Berlin, Heidelberg (1997)"},{"key":"10246_CR7","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979)"},{"issue":"5","key":"10246_CR8","doi-asserted-by":"publisher","first-page":"1339","DOI":"10.1007\/s00224-024-10169-9","volume":"68","author":"J Xie","year":"2024","unstructured":"Xie, J., Hunt, H.B., III.,Stearns, R.E.: Pumping lemmas can be \u201charmful\u2019\u2019. Theory Comput. Syst. 68(5), 1339\u20131352 (2024). https:\/\/doi.org\/10.1007\/s00224-024-10169-9","journal-title":"Theory Comput. Syst."},{"key":"10246_CR9","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H Rogers Jr","year":"1987","unstructured":"Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge, MA, USA (1987)"},{"key":"10246_CR10","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":"10246_CR11","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":"10246_CR12","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0304-3975(99)00129-2","volume":"250","author":"V Mihalache","year":"2001","unstructured":"Mihalache, V., Salomaa, A.: Language-theoretic aspects of dna complematarity. Theoret. Comput. Sci. 250(1), 163\u2013178 (2001). https:\/\/doi.org\/10.1016\/S0304-3975(99)00129-2","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"10246_CR13","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0020-0190(76)90062-4","volume":"5","author":"M Linna","year":"1976","unstructured":"Linna, M.: The d0l-ness for context-free languages is decidable. Inf. Process. Lett. 5(5), 149\u2013151 (1976). https:\/\/doi.org\/10.1016\/0020-0190(76)90062-4","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10246_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01691341","volume":"2","author":"S Greibach","year":"1968","unstructured":"Greibach, S.: A note on undecidable properties of formal languages. Math. Syst. Theory 2(1), 1\u20136 (1968)","journal-title":"Math. Syst. Theory"},{"issue":"1","key":"10246_CR15","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."},{"key":"10246_CR16","doi-asserted-by":"publisher","unstructured":"Xie, J., Hunt, H.B., III., Stearns, R.E.: On the computational and descriptional complexity of multi-pattern languages.\u00a0Theor. Comput. Sci. 1030, 115063 (2025). https:\/\/doi.org\/10.1016\/j.tcs.2025.115063","DOI":"10.1016\/j.tcs.2025.115063"},{"issue":"6","key":"10246_CR17","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. Found. Comput. Sci. 14(6), 1007\u20131018 (2003). https:\/\/doi.org\/10.1142\/S012905410300214X","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"10246_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)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10246_CR19","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0304-3975(94)00087-Y","volume":"141","author":"L Kari","year":"1995","unstructured":"Kari, L., Mateescu, A., P\u01ceun, G., Salomaa, A.: Multi-pattern languages. Theoret. Comput. Sci. 141(1), 253\u2013268 (1995). https:\/\/doi.org\/10.1016\/0304-3975(94)00087-Y","journal-title":"Theoret. Comput. Sci."},{"key":"10246_CR20","volume-title":"A Characterization of ET0L and EDT0L Languages","author":"PR Asveld","year":"1976","unstructured":"Asveld, P.R.: A Characterization of ET0L and EDT0L Languages. University of Twente, Netherlands, Department of Applied Mathematics (1976)"},{"key":"10246_CR21","volume-title":"Formal Languages and Their Relation to Automata","author":"JE Hopcroft","year":"1969","unstructured":"Hopcroft, J.E., Ullman, J.D.: Formal Languages and Their Relation to Automata. Addison-Wesley Longman Publishing Co., Inc, Boston, MA, USA (1969)"},{"issue":"3","key":"10246_CR22","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1145\/322017.322020","volume":"24","author":"HB Hunt III","year":"1977","unstructured":"Hunt, H.B., III., Rosenkrantz, D.J.: On equivalence and containment problems for formal languages. J. ACM 24(3), 387\u2013396 (1977). https:\/\/doi.org\/10.1145\/322017.322020","journal-title":"J. ACM"},{"issue":"1","key":"10246_CR23","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"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10246-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10246-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10246-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T08:52:51Z","timestamp":1769244771000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10246-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,11]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10246"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10246-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,11]]},"assertion":[{"value":"23 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"We (Jingnan Xie, Harry B. Hunt, III, and Richard E. Stearns) certify that we have NO affiliations with or involvement in any organization or entity with any financial interest, or non-financial interest in the subject matter or materials discussed in this manuscript.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}}],"article-number":"34"}}