{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T13:18:08Z","timestamp":1774271888016,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T00:00:00Z","timestamp":1769817600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T00:00:00Z","timestamp":1769817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Justus-Liebig-Universit\u00e4t Gie\u00dfen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In this paper, we continue the research on the power of contextual grammars with selection languages from subfamilies of the family of regular languages. In the past, two independent hierarchies have been obtained for external and internal contextual grammars, one based on selection languages defined by structural properties (finite, monoidal, nilpotent, combinational, definite, ordered, non-counting, power-separating, suffix-closed, commutative, circular, or union-free languages), the other one based on selection languages defined by resources (number of non-terminal symbols, production rules, or states needed for generating or accepting them). In a previous paper, the language families of these hierarchies for external contextual grammars were compared and the hierarchies merged. In the present paper, we compare the language families of these hierarchies for internal contextual grammars and merge these hierarchies.<\/jats:p>","DOI":"10.1007\/s00236-025-00520-z","type":"journal-article","created":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T07:14:33Z","timestamp":1769843673000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Internal contextual grammars with resources restricted and structure limited selection"],"prefix":"10.1007","volume":"63","author":[{"given":"Bianca","family":"Truthe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,31]]},"reference":[{"key":"520_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s00224-013-9515-7","volume":"54","author":"JA Brzozowski","year":"2014","unstructured":"Brzozowski, J.A., Jir\u00e1skov\u00e1, G., Zou, C.: Quotient complexity of closed languages. Theory of Computing Systems 54, 277\u2013292 (2014). https:\/\/doi.org\/10.1007\/s00224-013-9515-7","journal-title":"Theory of Computing Systems"},{"key":"520_CR2","volume-title":"Regular expression techniques for sequential circuits","author":"JA Brzozowski","year":"1962","unstructured":"Brzozowski, J.A.: Regular expression techniques for sequential circuits. PhD thesis, Princeton University, Princeton, NJ, USA (1962)"},{"issue":"1\u20134","key":"520_CR3","first-page":"109","volume":"64","author":"J Dassow","year":"2005","unstructured":"Dassow, J.: Contextual grammars with subregular choice. Fund. Inform. 64(1\u20134), 109\u2013118 (2005)","journal-title":"Fund. Inform."},{"issue":"1","key":"520_CR4","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.tcs.2012.04.008","volume":"449","author":"J Dassow","year":"2012","unstructured":"Dassow, J., Manea, F., Truthe, B.: On external contextual grammars with subregular selection languages. Theoret. Comput. Sci. 449(1), 64\u201373 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.04.008","journal-title":"Theoret. Comput. Sci."},{"issue":"2\u20134","key":"520_CR5","doi-asserted-by":"publisher","first-page":"145","DOI":"10.25596\/jalc-2012-145","volume":"17","author":"J Dassow","year":"2012","unstructured":"Dassow, J., Manea, F., Truthe, B.: On subregular selection languages in internal contextual grammars. J. Autom. Lang. Comb. 17(2\u20134), 145\u2013164 (2012). https:\/\/doi.org\/10.25596\/jalc-2012-145","journal-title":"J. Autom. Lang. Comb."},{"issue":"1\u20132","key":"520_CR6","first-page":"87","volume":"15","author":"J Dassow","year":"1979","unstructured":"Dassow, J.: On the circular closure of languages. Elektronische Informationsverarbeitung und Kybernetik\/Journal of Information Processing and Cybernetics 15(1\u20132), 87\u201394 (1979)","journal-title":"Elektronische Informationsverarbeitung und Kybernetik\/Journal of Information Processing and Cybernetics"},{"key":"520_CR7","first-page":"25","volume":"62","author":"J Dassow","year":"2015","unstructured":"Dassow, J.: Contextual languages with strictly locally testable and star free selection languages. Analele Universit\u0103\u021bii Bucureti 62, 25\u201336 (2015)","journal-title":"Analele Universit\u0103\u021bii Bucureti"},{"issue":"1\u20133","key":"520_CR8","doi-asserted-by":"publisher","first-page":"143","DOI":"10.25596\/jalc-2018-143","volume":"23","author":"J Dassow","year":"2018","unstructured":"Dassow, J.: Grammars with control by ideals and codes. J. Autom. Lang. Comb. 23(1\u20133), 143\u2013164 (2018). https:\/\/doi.org\/10.25596\/jalc-2018-143","journal-title":"J. Autom. Lang. Comb."},{"key":"520_CR9","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.tcs.2020.07.028","volume":"862","author":"J Dassow","year":"2021","unstructured":"Dassow, J.: Remarks on external contextual grammars with selection. Theoretical Computer Science 862, 119\u2013129 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2020.07.028","journal-title":"Theoretical Computer Science"},{"key":"520_CR10","volume-title":"Algebraic Theory of Automata","author":"F G\u00e9cseg","year":"1972","unstructured":"G\u00e9cseg, F., Peak, I.: Algebraic Theory of Automata. Academiai Kiado, Budapest (1972)"},{"issue":"1","key":"520_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/s0022-0000(74)80034-6","volume":"9","author":"A Gill","year":"1974","unstructured":"Gill, A., Kou, L.T.: Multiple-entry finite automata. Journal of Computer and System Sciences 9(1), 1\u201319 (1974). https:\/\/doi.org\/10.1016\/s0022-0000(74)80034-6","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"520_CR12","first-page":"520","volume":"5","author":"IM Havel","year":"1969","unstructured":"Havel, I.M.: The theory of regular events II. Kybernetika 5(6), 520\u2013544 (1969)","journal-title":"Kybernetika"},{"key":"520_CR13","first-page":"287","volume":"30","author":"S Istrail","year":"1978","unstructured":"Istrail, S.: Gramatici contextuale cu selectiva regulata. Stud. Cerc. Mat. 30, 287\u2013294 (1978)","journal-title":"Stud. Cerc. Mat."},{"key":"520_CR14","first-page":"1525","volume":"14","author":"S Marcus","year":"1969","unstructured":"Marcus, S.: Contextual grammars. Revue Roum. Math. Pures Appl. 14, 1525\u20131534 (1969)","journal-title":"Revue Roum. Math. Pures Appl."},{"key":"520_CR15","volume-title":"Counter-free Automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-free Automata. MIT Press, Cambridge, USA (1971)"},{"key":"520_CR16","unstructured":"Truthe, B.: A relation between definite and ordered finite automata. In: Bensch, S., Freund, R., Otto, F. (eds.) Sixth Workshop on Non-Classical Models of Automata and Applications (NCMA), Kassel, Germany, July 28\u201329, 2014, Proceedings. books@ocg.at, vol. 304, pp. 235\u2013247. \u00d6sterreichische Computer Gesellschaft, Wien (2014)"},{"key":"520_CR17","unstructured":"Truthe, B.: Hierarchy of subregular language families. Technical report, Justus-Liebig-Universit\u00e4t Giessen, Institut f\u00fcr Informatik, IFIG Research Report 1801 (2018)"},{"key":"520_CR18","doi-asserted-by":"publisher","unstructured":"Truthe, B.: Merging two hierarchies of external contextual grammars with subregular selection. In: Bordihn, H., Tran, N., Vaszil, Gy. (eds.) 25th International Conference on Descriptional Complexity of Formal Systems, DCFS 2023, Potsdam, Germany, July 4\u20136, 2023, Proceedings. LNCS, vol. 13918, pp. 169\u2013180. Springer, Berlin (2023). https:\/\/doi.org\/10.1007\/978-3-031-34326-1_13","DOI":"10.1007\/978-3-031-34326-1_13"},{"key":"520_CR19","doi-asserted-by":"publisher","unstructured":"Dassow, J., Manea, F., Truthe, B.: On Contextual grammars with subregular selection languages. In: Holzer, M., Kutrib, M., Pighizzini, G. (eds.) Descriptional Complexity of Formal Systems \u2013 13th International Workshop, DCFS 2011, Gie\u00dfen\/Limburg, Germany, July 25\u00a0\u2013\u00a027, 2011. Proceedings. LNCS, vol. 6808, pp. 135\u2013146. Springer, Berlin (2011). https:\/\/doi.org\/10.1007\/978-3-642-22600-7_11","DOI":"10.1007\/978-3-642-22600-7_11"},{"key":"520_CR20","doi-asserted-by":"publisher","unstructured":"Manea, F., Truthe, B.: On Internal contextual grammars with subregular selection languages. In: Kutrib, M., Moreira, N., Reis, R. (eds.) Descriptional Complexity of Formal Systems \u2013 14th International Workshop, DCFS 2012, Braga, Portugal, July 23\u00a0\u2013\u00a025, 2012. Proceedings. LNCS, vol. 7386, pp. 222\u2013235. Springer, Berlin (2012). https:\/\/doi.org\/10.1007\/978-3-642-31623-4_17","DOI":"10.1007\/978-3-642-31623-4_17"},{"key":"520_CR21","doi-asserted-by":"publisher","unstructured":"Dassow, J., Truthe, B.: On the generative capacity of contextual grammars with strictly locally testable selection languages. In: Bordihn, H., Horv\u00e1th, G., Vaszil (eds.) 12th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2022), Debrecen, Hungary, August 26\u00a0\u2013\u00a027, 2022. Proceedings. EPTCS, vol. 367, pp. 65\u201380. Open Publishing Association, Waterloo, Australia (2022). https:\/\/doi.org\/10.4204\/EPTCS.367.5","DOI":"10.4204\/EPTCS.367.5"},{"key":"520_CR22","volume-title":"Marcus Contextual Grammars","author":"G P\u0103un","year":"1998","unstructured":"P\u0103un, G.: Marcus Contextual Grammars. Kluwer Publ. House, Doordrecht (1998)"},{"key":"520_CR23","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1109\/PGEC.1963.263534","volume":"12","author":"M Perles","year":"1963","unstructured":"Perles, M., Rabin, M.M., Shamir, E.: The theory of definite automata. IEEE Trans. Electronic Computers 12, 233\u2013243 (1963). https:\/\/doi.org\/10.1109\/PGEC.1963.263534","journal-title":"IEEE Trans. Electronic Computers"},{"key":"520_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6","volume-title":"Handbook of Formal Languages","author":"G Rozenberg","year":"1997","unstructured":"Rozenberg, G., Salomaa, A.: Handbook of Formal Languages. Springer, Berlin (1997)"},{"key":"520_CR25","volume-title":"Free Monoids and Languages","author":"HJ Shyr","year":"1991","unstructured":"Shyr, H.J.: Free Monoids and Languages. Hon Min Book Co., Taichung, Taiwan (1991)"},{"issue":"1","key":"520_CR26","first-page":"9","volume":"5","author":"HJ Shyr","year":"1974","unstructured":"Shyr, H.J., Thierrin, G.: Ordered Automata and Associated Languages. Tankang Journal of Mathematics 5(1), 9\u201320 (1974)","journal-title":"Tankang Journal of Mathematics"},{"issue":"1","key":"520_CR27","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/BF01761710","volume":"8","author":"HJ Shyr","year":"1974","unstructured":"Shyr, H.J., Thierrin, G.: Power-Separating Regular Languages. Mathematical Systems Theory 8(1), 90\u201395 (1974). https:\/\/doi.org\/10.1007\/BF01761710","journal-title":"Mathematical Systems Theory"},{"key":"520_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3233\/FI-2021-2037","volume":"180","author":"B Truthe","year":"2021","unstructured":"Truthe, B.: Generative capacity of contextual grammars with subregular selection languages. Fund. Inform. 180, 1\u201328 (2021). https:\/\/doi.org\/10.3233\/FI-2021-2037","journal-title":"Fund. Inform."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00520-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00520-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00520-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T12:25:39Z","timestamp":1774268739000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00520-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,31]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["520"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00520-z","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,31]]},"assertion":[{"value":"12 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2026","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"}}],"article-number":"5"}}