{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:23:28Z","timestamp":1725665008318},"publisher-location":"Berlin, Heidelberg","reference-count":20,"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_32","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:51:01Z","timestamp":1330278661000},"page":"440-453","source":"Crossref","is-referenced-by-count":0,"title":["On the complexity of iterated insertions"],"prefix":"10.1007","author":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus-J\u00f6rn","family":"Lange","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I, volume 11 of EATCS Monographs on Theoretical Computer Science. Springer, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"32_CR2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. A. Cook","year":"1971","unstructured":"S. A. Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the ACM, 18:4\u201318, 1971.","journal-title":"Journal of the ACM"},{"key":"32_CR3","doi-asserted-by":"crossref","unstructured":"J. Dassow and K.-J. Lange. Complexity of automata with abstract storages. In Proceedings of the 8th Fundamentals of Computing Theory, number 529 in LNCS, pages 200\u2013209. Springer, 1991.","DOI":"10.1007\/3-540-54458-5_64"},{"key":"32_CR4","unstructured":"P. Flajolet and J. Steyaert. Complexity of classes of languages and operators. Rap. de Recherche 92, IRIA Laboria, 1974."},{"key":"32_CR5","volume-title":"Algebraic and Automata-Theoretic Properties of Formal Languages","author":"S. Ginsburg","year":"1975","unstructured":"S. Ginsburg. Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland, Amsterdam, 1975."},{"issue":"4","key":"32_CR6","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. A. Greibach","year":"1973","unstructured":"S. A. Greibach. The hardest context-free language. SIAM Journal on Computing, 2(4):304\u2013310, December 1973.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR7","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/S0022-0000(71)80023-5","volume":"5","author":"J. Gruska","year":"1971","unstructured":"J. Gruska. A characterization of context-free languages. Journal of Computer and System Sciences, 5:353\u2013364, 1971.","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR8","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0022-0000(84)90018-7","volume":"28","author":"D. Haussler","year":"1984","unstructured":"D. Haussler and M. K. Warmuth. On the complexity of iterated shuffle. Journal of Computer and System Sciences, 28:345\u2013358, 1984.","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR9","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979."},{"key":"32_CR10","first-page":"181","volume":"51","author":"L. Kari","year":"1993","unstructured":"L. Kari. Insertion operations: closure properties. Bulletin of the European Association for Theoretical Computer Science, 51:181\u2013191, 1993.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"32_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(85)90085-4","volume":"37","author":"K.-I. Ko","year":"1985","unstructured":"K.-I. Ko. On some natural complete operations. Theoretical Computer Science, 37:1\u201330, 1985.","journal-title":"Theoretical Computer Science"},{"key":"32_CR12","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. Ladner","year":"1976","unstructured":"R. Ladner and N. Lynch. Relativization of questions about log space computability. Mathematical Systems Theory, 10:19\u201332, 1976.","journal-title":"Mathematical Systems Theory"},{"key":"32_CR13","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0304-3975(88)90025-4","volume":"58","author":"K.-J. Lange","year":"1988","unstructured":"K.-J. Lange. Decomposition of nondeterministic reductions. Theoretical Computer Science, 58:175\u2013181, 1988.","journal-title":"Theoretical Computer Science"},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"K.-J. Lange. Complexity structure in formal language theory. In Proceedings of the 8th Annual Structure in Complexity Theory, pages 224\u2013238. IEEE Computer Society Press, May 1993.","DOI":"10.1109\/SCT.1993.336523"},{"key":"32_CR15","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1016\/S0022-0000(71)80020-X","volume":"5","author":"I. P. McWhirter","year":"1971","unstructured":"I. P. McWhirter. Substitution expressions. Journal of Computer and System Sciences, 5:629\u2013637, 1971.","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR16","doi-asserted-by":"crossref","unstructured":"B. Monien. About the deterministic simulation of nondeterministic (log n)-tape bounded Turing machines. In 2-te GI Fachtagung Automatentheorie und Formale Sprachen, number 33 in LNCS, pages 118\u2013126. Springer, 1975.","DOI":"10.1007\/3-540-07407-4_15"},{"key":"32_CR17","first-page":"287","volume-title":"Formal Languages\u2014Perspectives and Open Problems","author":"B. Monien","year":"1980","unstructured":"B. Monien and I. Sudborough. The interface between language theory and complexity theory. In R. V. Book, editor, Formal Languages\u2014Perspectives and Open Problems, pages 287\u2013324, New York, 1980. Academic Press."},{"key":"32_CR18","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","volume":"28","author":"W. L. Ruzzo","year":"1984","unstructured":"W. L. Ruzzo, J. Simon, and M. Tompa. Space-bounded hierarchies and probabilistic computations. Journal of Computer and System Sciences, 28:216\u2013230, 1984.","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR19","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. H. Sudborough","year":"1978","unstructured":"I. H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the ACM, 25:405\u2013414, 1978.","journal-title":"Journal of the ACM"},{"key":"32_CR20","volume-title":"Mathematics and its applications (East Europeans series)","author":"K. Wagner","year":"1986","unstructured":"K. Wagner and G. Wechsung. Computational Complexity. Mathematics and its applications (East Europeans series). VEB Deutscher Verlag der Wissenschaften, Berlin, 1986."}],"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_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:14:25Z","timestamp":1605629665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62844-4_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540628446","9783540687030"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-62844-4_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}