{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:43:59Z","timestamp":1759063439237,"version":"3.40.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,2,11]],"date-time":"2012-02-11T00:00:00Z","timestamp":1328918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2012,3]]},"DOI":"10.1007\/s00236-012-0150-6","type":"journal-article","created":{"date-parts":[[2012,2,10]],"date-time":"2012-02-10T09:24:01Z","timestamp":1328865841000},"page":"55-68","source":"Crossref","is-referenced-by-count":5,"title":["Nonterminal complexity of one-sided random context grammars"],"prefix":"10.1007","volume":"49","author":[{"given":"Alexander","family":"Meduna","sequence":"first","affiliation":[]},{"given":"Petr","family":"Zemek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,2,11]]},"reference":[{"key":"150_CR1","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1016\/j.ipl.2010.07.008","volume":"110","author":"E. Csuhaj-Varj\u00fa","year":"2010","unstructured":"Csuhaj-Varj\u00fa E., Vaszil G.: Scattered context grammars generate any recursively enumerable language with two nonterminals. Inf. Process. Lett. 110, 902\u2013907 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"35","key":"150_CR2","doi-asserted-by":"crossref","first-page":"3250","DOI":"10.1016\/j.tcs.2009.05.001","volume":"410","author":"E. Czeizler","year":"2009","unstructured":"Czeizler E., Czeizler E., Kari L., Salomaa K.: On the descriptional complexity of Watson\u2013Crick automata. Theor Comput Sci 410(35), 3250\u20133260 (2009)","journal-title":"Theor Comput Sci"},{"key":"150_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-74932-2","volume-title":"Regulated Rewriting in Formal Language Theory","author":"J. Dassow","year":"1989","unstructured":"Dassow J., P\u0103un G.: Regulated Rewriting in Formal Language Theory. Springer, New York, NY (1989)"},{"issue":"2","key":"150_CR4","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0304-3975(02)00656-4","volume":"296","author":"H. Fernau","year":"2003","unstructured":"Fernau H.: Nonterminal complexity of programmed grammars. Theor. Comput. Sci. 296(2), 225\u2013251 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"150_CR5","first-page":"117","volume":"12","author":"H. Fernau","year":"2007","unstructured":"Fernau H., Freund R., Oswald M., Reinhardt K.: Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars. J. Automat. Lang. Comb. 12(1\u20132), 117\u2013138 (2007)","journal-title":"J. Automat. Lang. Comb."},{"issue":"5","key":"150_CR6","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/S0020-0190(03)00202-3","volume":"86","author":"H. Fernau","year":"2003","unstructured":"Fernau H., Meduna A.: A simultaneous reduction of several measures of descriptional complexity in scattered context grammars. Inf. Process. Lett. 86(5), 235\u2013240 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"150_CR7","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1051\/ita\/1991250504731","volume":"25","author":"V. Geffert","year":"1991","unstructured":"Geffert V.: Normal forms for phrase-structure grammars. Theor. Inf. Appl. 25(5), 473\u2013496 (1991)","journal-title":"Theor. Inf. Appl."},{"key":"150_CR8","doi-asserted-by":"crossref","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic finite automata\u2014recent results on the descriptional and computational complexity. In: Implementation and Applications of Automata, Lecture Notes in Computer Science, vol. 5148, pp. 1\u201316. Springer (2008)","DOI":"10.1007\/978-3-540-70844-5_1"},{"issue":"2\u20133","key":"150_CR9","first-page":"311","volume":"9","author":"M. Madhu","year":"2004","unstructured":"Madhu M.: Descriptional complexity of rewriting P systems. J. Autom. Lang. Comb. 9(2\u20133), 311\u2013316 (2004)","journal-title":"J. Autom. Lang. Comb."},{"key":"150_CR10","doi-asserted-by":"crossref","unstructured":"Mart\u00edn-Vide, C., Mitrana, V., P\u0103un, G. (eds.): Formal Languages and Applications, chap. 13. pp. 249\u2013274. Springer Berlin (2004)","DOI":"10.1007\/978-3-540-39886-8"},{"issue":"2","key":"150_CR11","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ipl.2008.04.002","volume":"108","author":"T. Masopust","year":"2008","unstructured":"Masopust T.: Descriptional complexity of multi-parallel grammars. Inf. Process. Lett. 108(2), 68\u201370 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"150_CR12","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/j.tcs.2008.10.017","volume":"410","author":"T. Masopust","year":"2009","unstructured":"Masopust T.: On the descriptional complexity of scattered context grammars. Theor. Comput. Sci. 410(1), 108\u2013112 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"150_CR13","doi-asserted-by":"crossref","first-page":"407","DOI":"10.3233\/FUN-2008-873-406","volume":"87","author":"T. Masopust","year":"2008","unstructured":"Masopust T., Meduna A.: On descriptional complexity of partially parallel grammars. Fundamenta Informaticae 87(3), 407\u2013415 (2008)","journal-title":"Fundamenta Informaticae"},{"key":"150_CR14","doi-asserted-by":"crossref","unstructured":"Masopust, T., Meduna, A.: Descriptional complexity of three-nonterminal scattered context grammars: an improvement. In: Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems, pp. 235\u2013245. Otto-von-Guericke-Universit\u00e4t Magdeburg (2009)","DOI":"10.4204\/EPTCS.3.17"},{"key":"150_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-0501-5","volume-title":"Automata and Languages: Theory and Applications","author":"A. Meduna","year":"2000","unstructured":"Meduna A.: Automata and Languages: Theory and Applications. Springer, London (2000)"},{"issue":"3","key":"150_CR16","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s00236-011-0134-y","volume":"48","author":"A. Meduna","year":"2011","unstructured":"Meduna A., Zemek P.: One-sided random context grammars. Acta Informatica 48(3), 149\u2013163 (2011)","journal-title":"Acta Informatica"},{"issue":"1","key":"150_CR17","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.ipl.2009.10.002","volume":"110","author":"F. Okubo","year":"2009","unstructured":"Okubo F.: A note on the descriptional complexity of semi-conditional grammars. Inf. Process. Lett. 110(1), 36\u201340 (2009)","journal-title":"Inf. Process. Lett."},{"volume-title":"Handbook of Formal Languages, vol. 1\u20133","year":"1997","key":"150_CR18","unstructured":"Rozenberg, G., Salomaa, A. (eds): Handbook of Formal Languages, vol. 1\u20133. Springer, Berlin (1997)"},{"issue":"2","key":"150_CR19","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/j.tcs.2004.06.032","volume":"330","author":"G. Vaszil","year":"2005","unstructured":"Vaszil G.: On the descriptional complexity of some rewriting mechanisms regulated by context conditions. Theor. Comput. Sci. 330(2), 361\u2013373 (2005)","journal-title":"Theor. Comput. Sci."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-012-0150-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-012-0150-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-012-0150-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,20]],"date-time":"2025-03-20T08:03:55Z","timestamp":1742457835000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-012-0150-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,11]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["150"],"URL":"https:\/\/doi.org\/10.1007\/s00236-012-0150-6","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2012,2,11]]}}}