{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T11:04:41Z","timestamp":1717067081807},"reference-count":20,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3886,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2003,1]]},"DOI":"10.1016\/s0890-5401(02)00013-5","type":"journal-article","created":{"date-parts":[[2003,1,17]],"date-time":"2003-01-17T17:34:03Z","timestamp":1042824843000},"page":"101-112","source":"Crossref","is-referenced-by-count":8,"title":["Bounded size dictionary compression: SCk-completeness and NC algorithms"],"prefix":"10.1016","volume":"180","author":[{"given":"Sergio","family":"De Agostino","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Silvestri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0890-5401(02)00013-5_BIB1","series-title":"Text Compression","author":"Bell","year":"1990"},{"key":"10.1016\/S0890-5401(02)00013-5_BIB2","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","article-title":"On relating time and space to size and depth","volume":"6","author":"Borodin","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0890-5401(02)00013-5_BIB3","series-title":"11th Ann. ACM Symposium on Theory of Computing","first-page":"338","article-title":"Deterministic CFL\u2019s are accepted simultaneously in polynomial time and log squared space","author":"Cook","year":"1979"},{"key":"10.1016\/S0890-5401(02)00013-5_BIB4","first-page":"99","article-title":"Towards a complexity theory of synchronous parallel computation","volume":"27","author":"Cook","year":"1981","journal-title":"Enseign. Math."},{"key":"10.1016\/S0890-5401(02)00013-5_BIB5","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","article-title":"A taxonomy of problems with fast parallel algorithms","volume":"64","author":"Cook","year":"1985","journal-title":"Inf. Control"},{"key":"10.1016\/S0890-5401(02)00013-5_BIB6","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0020-0190(91)90223-5","article-title":"Efficient parallel algorithms to test square-freeness and factorize strings","volume":"38","author":"Crochemore","year":"1991","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/S0890-5401(02)00013-5_BIB7","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(94)90106-6","article-title":"P-complete problems in data compression","volume":"127","author":"De Agostino","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/S0890-5401(02)00013-5_BIB8","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/S0304-3975(99)00314-X","article-title":"Erratum to P-complete problems in data compression","volume":"234","author":"De Agostino","year":"2000","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/S0890-5401(02)00013-5_BIB9","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0304-3975(94)00213-3","article-title":"Multi-list layering: complexity and applications","volume":"141","author":"Dessmark","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/S0890-5401(02)00013-5_BIB10","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0890-5401(89)90009-6","article-title":"Complexity theory of parallel time and hardware","volume":"80","author":"Dymond","year":"1989","journal-title":"Inf. Comput."},{"key":"10.1016\/S0890-5401(02)00013-5_BIB11","series-title":"Limits to Parallel Computation","author":"Greenlaw","year":"1995"},{"key":"10.1016\/S0890-5401(02)00013-5_BIB12","series-title":"Handbook of Theoretical Computer Science: Algorithms and Complexity","first-page":"67","article-title":"A catalog of complexity classes","author":"Johnson","year":"1990"},{"key":"10.1016\/S0890-5401(02)00013-5_BIB13","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Lempel","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/S0890-5401(02)00013-5_BIB14","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1109\/71.139209","article-title":"Optimal parallel algorithms for problems modeled by a family of intervals","volume":"3","author":"Olariu","year":"1992","journal-title":"IEEE Trans. Parallel Distributed Syst."},{"key":"10.1016\/S0890-5401(02)00013-5_BIB15","series-title":"20th Ann. Symposium on Foundations of Computer Science","first-page":"307","article-title":"On simultaneous resource bounds","author":"Pippenger","year":"1979"},{"key":"10.1016\/S0890-5401(02)00013-5_BIB16","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","article-title":"Relations among complexity measures","volume":"26","author":"Pippenger","year":"1979","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0890-5401(02)00013-5_BIB17","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","article-title":"On uniform circuit complexity","volume":"22","author":"Ruzzo","year":"1981","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/S0890-5401(02)00013-5_BIB18","series-title":"Data Compression: Methods and Theory","author":"Storer","year":"1988"},{"key":"10.1016\/S0890-5401(02)00013-5_BIB19","series-title":"Image and Text Compression","first-page":"159","article-title":"Massively parallel systolic algorithms for real-time dictionary-based text compression","author":"Storer","year":"1992"},{"key":"10.1016\/S0890-5401(02)00013-5_BIB20","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540102000135?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540102000135?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,30]],"date-time":"2019-03-30T17:20:48Z","timestamp":1553966448000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540102000135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["S0890540102000135"],"URL":"https:\/\/doi.org\/10.1016\/s0890-5401(02)00013-5","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}