{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T08:59:35Z","timestamp":1754557175783},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540628446"},{"type":"electronic","value":"9783540687030"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-62844-4_17","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:50:35Z","timestamp":1330278635000},"page":"247-255","source":"Crossref","is-referenced-by-count":1,"title":["A grammar characterization of logarithmic-space computation"],"prefix":"10.1007","author":[{"given":"Karl","family":"Abrahamson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liming","family":"Cai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steve","family":"Gordon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz and J. Gabarr\u00f3, Structural Complexity I and II, (Springer-Verlag, 1990).","DOI":"10.1007\/978-3-642-75357-2"},{"key":"17_CR2","first-page":"209","volume-title":"The computational complexity of PCGS with regular components","author":"L. Cai","year":"1996","unstructured":"L. Cai, The computational complexity of PCGS with regular components. Proceedings 2nd International Conference on Development in Language Theory, World Sci. Publ., Singapore, 1996, 209\u2013219."},{"issue":"2\u20133","key":"17_CR3","first-page":"199","volume":"15","author":"L. Cai","year":"1996","unstructured":"L. Cai, The complexity of linear PCGSs, Computers and Artificial Intelligence, 15, 2\u20133 (1996), pp. 199\u2013210.","journal-title":"Computers and Artificial Intelligence"},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"S. Cook, A Taxonomy of problems with fast parallel algorithms, Information and Control, 64 (1985), 2\u201322.","journal-title":"Information and Control"},{"key":"17_CR5","unstructured":"E. Csuhaj-Varj\u00fa, J. Dassow, J. Kelemen, and Gh. P\u0103un, Grammar Systems, (Gordon and Breach Sci. Publishers Ltd., 1993)."},{"key":"17_CR6","unstructured":"R. Freund, Gh. P\u0103un, C. Procopiuc and O. Procopiuc, Parallel Communicating Grammar Systems with Context-sensitive Components, Artificial Life: Grammatical Models, Gh. P\u0103un ed. (The Black sea Univ. Press, 1995)."},{"key":"17_CR7","unstructured":"J. E. Hopcroft and J. D. Ullman, Introduction to automata theory, languages and computation (Addison Wesley, 1979)."},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, J. Kari and L. Kari, Some hierarchies for the communication complexity measures of cooperating grammar systems, Theoretical computer Science, 127, 123\u2013147.","DOI":"10.1016\/0304-3975(94)90103-1"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, J. Kari, L. Kari and J. Pardubsk\u00e1, Two lower bounds on distributive generation of languages, Proc. 19th MFCS'94, Lecture Notes in Computer Science 841, 423\u2013432.","DOI":"10.1007\/3-540-58338-6_89"},{"key":"17_CR10","unstructured":"J. Hromkovi\u010d and D. Wierzchula, Note on nondeterministic linear time, real time, and parallel communicating grammar systems, manuscript."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"D. S. Johnson, A catalog for complexity classes, in: J. van Leeuvan, ed., The handbook of Theoretical Computer Sciences Vol A (Elsevier Science Publishers, 1990), 69\u2013161.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"17_CR12","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF01209710","volume":"30","author":"G. P\u0103un","year":"1993","unstructured":"Gh. P\u0103un, On the synchronization in parallel communicating grammar systems, Acta Informatica, 30 (1993), 351\u2013367.","journal-title":"Acta Informatica"},{"key":"17_CR13","first-page":"55","volume":"38","author":"G. P\u0103un","year":"1989","unstructured":"Gh. P\u0103un and L. Santean, Parallel communicating grammar systems: the regular case, Ann. Univ. Buc., Series Matem.-Inform., 38 (1989), 55\u201363.","journal-title":"Ann. Univ. Buc., Series Matem.-Inform."},{"key":"17_CR14","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1080\/00207169008803876","volume":"34","author":"G. P\u0103un","year":"1990","unstructured":"Gh. P\u0103un and L. Santean, Further remarks on parallel communicating grammar systems, International Journal on Computing Mathematics, 34 (1990), 187\u2013203.","journal-title":"International Journal on Computing Mathematics"},{"key":"17_CR15","unstructured":"A. Salomaa, Formal Languages (Academic Press, 1973)."},{"key":"17_CR16","first-page":"160","volume":"42","author":"L. Santean","year":"1990","unstructured":"L. Santean, Parallel communicating systems, Bulletin EATCS, 42 (1990), 160\u2013171.","journal-title":"Bulletin EATCS"},{"key":"17_CR17","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(92)90003-X","volume":"98","author":"L. Santean","year":"1992","unstructured":"L. Santean and J. Kari, The impact of the number of cooperating grammars on the generative power, Theoretical Computer Science, 98 (1992), 249\u2013262.","journal-title":"Theoretical Computer Science"},{"key":"17_CR18","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. Sudborough","year":"1978","unstructured":"I. Sudborough, On the tape complexity of deterministic context-free languages, Journal of ACM, 25 (1978), 405\u2013414.","journal-title":"Journal of ACM"}],"container-title":["Lecture Notes in Computer Science","New Trends in Formal Languages"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62844-4_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:14:20Z","timestamp":1605629660000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62844-4_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540628446","9783540687030"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-62844-4_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}