{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:51:26Z","timestamp":1740106286298,"version":"3.37.3"},"reference-count":49,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2023,4,26]],"date-time":"2023-04-26T00:00:00Z","timestamp":1682467200000},"content-version":"am","delay-in-days":602,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/100005651","name":"Computing Research Association","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005651","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1016\/j.jcss.2021.02.004","type":"journal-article","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T02:50:17Z","timestamp":1616122217000},"page":"162-176","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Closure and nonclosure properties of the classes of compressible and rankable sets"],"prefix":"10.1016","volume":"120","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7825-9886","authenticated-orcid":false,"given":"Jackson","family":"Abascal","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0659-5204","authenticated-orcid":false,"given":"Lane A.","family":"Hemaspaandra","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5683-734X","authenticated-orcid":false,"given":"Shir","family":"Maimon","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Rubery","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"author":"Aaronson","key":"10.1016\/j.jcss.2021.02.004_br0010"},{"author":"Abascal","key":"10.1016\/j.jcss.2021.02.004_br0020"},{"key":"10.1016\/j.jcss.2021.02.004_br0030","series-title":"Proceedings of the 13th International Conference on Language and Automata Theory and Applications","first-page":"177","article-title":"Closure and nonclosure properties of the compressible and rankable sets","volume":"vol. 11417","author":"Abascal","year":"2019"},{"year":"1985","series-title":"Invertible functions","author":"Allender","key":"10.1016\/j.jcss.2021.02.004_br0040"},{"issue":"3","key":"10.1016\/j.jcss.2021.02.004_br0050","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1007\/s00224-011-9334-7","article-title":"Avoiding simplicity is complex","volume":"51","author":"Allender","year":"2012","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.jcss.2021.02.004_br0060","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","article-title":"A very hard log-space counting class","volume":"107","author":"\u00c1lvarez","year":"1993","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.jcss.2021.02.004_br0070","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1137\/0215053","article-title":"Sparse sets, lowness and highness","volume":"15","author":"Balc\u00e1zar","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2021.02.004_br0080","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-79235-9","article-title":"Structural Complexity I","author":"Balc\u00e1zar","year":"1995"},{"issue":"2","key":"10.1016\/j.jcss.2021.02.004_br0090","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(91)90023-U","article-title":"The complexity of computing the number of strings of given length in context-free languages","volume":"86","author":"Bertoni","year":"1991","journal-title":"Theor. Comput. Sci."},{"year":"1978","series-title":"A note on cryptography and NP\u2229coNP\u2212P","author":"Brassard","key":"10.1016\/j.jcss.2021.02.004_br0100"},{"issue":"3","key":"10.1016\/j.jcss.2021.02.004_br0110","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1137\/S009753979834388X","article-title":"Resource-bounded Kolmogorov complexity revisited","volume":"31","author":"Buhrman","year":"2001","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2021.02.004_br0120","series-title":"Proceedings of the 13th International Conference on Algorithmic Aspects in Information and Management","first-page":"16","article-title":"Improved algorithms for ranking and unranking (k,m)-ary trees","volume":"vol. 11640","author":"Chang","year":"2019"},{"key":"10.1016\/j.jcss.2021.02.004_br0130","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.jcss.2016.07.003","article-title":"Closure properties of pattern languages","volume":"84","author":"Day","year":"2017","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.jcss.2021.02.004_br0140","series-title":"Proceedings of the 5th Symposium in Pure Mathematics","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1090\/pspum\/005\/0142447","article-title":"Infinite series of isols","author":"Dekker","year":"1962"},{"key":"10.1016\/j.jcss.2021.02.004_br0150","doi-asserted-by":"crossref","first-page":"357","DOI":"10.4153\/CJM-1958-035-x","article-title":"Retraceable sets","volume":"10","author":"Dekker","year":"1958","journal-title":"Can. J. Math."},{"key":"10.1016\/j.jcss.2021.02.004_br0160","series-title":"Proceedings of the 36th Annual Symposium on Theoretical Aspects of Computer Science","first-page":"22:1","article-title":"Closure properties of synchronized relations","volume":"vol. 126","author":"Descotte","year":"2019"},{"issue":"1","key":"10.1016\/j.jcss.2021.02.004_br0170","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/S0890-5401(03)00119-6","article-title":"Inverting onto functions","volume":"186","author":"Fenner","year":"2003","journal-title":"Inf. Comput."},{"issue":"3","key":"10.1016\/j.jcss.2021.02.004_br0180","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1137\/0220034","article-title":"Compression and ranking","volume":"20","author":"Goldberg","year":"1991","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.jcss.2021.02.004_br0190","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/BF01276437","article-title":"Polynomial-time compression","volume":"2","author":"Goldsmith","year":"1992","journal-title":"Comput. Complex."},{"issue":"3","key":"10.1016\/j.jcss.2021.02.004_br0200","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0020-0190(95)00204-9","article-title":"Scalability and the isomorphism problem","volume":"57","author":"Goldsmith","year":"1996","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10.1016\/j.jcss.2021.02.004_br0210","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1006\/inco.1999.2810","article-title":"NP sets and easy census functions","volume":"158","author":"Goldsmith","year":"2000","journal-title":"Inf. Comput."},{"issue":"2","key":"10.1016\/j.jcss.2021.02.004_br0220","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/0217018","article-title":"Complexity measures for public-key cryptosystems","volume":"17","author":"Grollmann","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2021.02.004_br0230","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.tcs.2019.04.007","article-title":"Ranking and unranking fixed-density necklaces and Lyndon words","volume":"791","author":"Hartman","year":"2019","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10.1016\/j.jcss.2021.02.004_br0240","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0022-0000(90)90038-M","article-title":"On the complexity of ranking","volume":"41","author":"Hemachandra","year":"1990","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"10.1016\/j.jcss.2021.02.004_br0250","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/0304-3975(94)00290-Y","article-title":"Intersections and indices","volume":"145","author":"Hemaspaandra","year":"1995","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"10.1016\/j.jcss.2021.02.004_br0260","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0304-3975(98)00006-1","article-title":"Boolean operations, joins, and the extended low hierarchy","volume":"205","author":"Hemaspaandra","year":"1998","journal-title":"Theor. Comput. Sci."},{"issue":"11","key":"10.1016\/j.jcss.2021.02.004_br0270","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1007\/s002360050109","article-title":"Easy sets and hard certificate schemes","volume":"34","author":"Hemaspaandra","year":"1997","journal-title":"Acta Inform."},{"key":"10.1016\/j.jcss.2021.02.004_br0280","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.jcss.2018.10.003","article-title":"Recursion-theoretic ranking and compression","volume":"101","author":"Hemaspaandra","year":"2019","journal-title":"J. Comput. Syst. Sci."},{"year":"2003","series-title":"Theory of Semi-Feasible Algorithms","author":"Hemaspaandra","key":"10.1016\/j.jcss.2021.02.004_br0290"},{"issue":"1","key":"10.1016\/j.jcss.2021.02.004_br0300","first-page":"50","article-title":"Polynomial-time semi-rankable sets","volume":"2","author":"Hemaspaandra","year":"1996","journal-title":"Journal of Computing and Information"},{"key":"10.1016\/j.jcss.2021.02.004_br0310","series-title":"Proceedings of the 20th Annual IEEE Conference on Computational Complexity","first-page":"28","article-title":"The complexity of the inertia and some closure properties of GapL","author":"Hoang","year":"2005"},{"issue":"1","key":"10.1016\/j.jcss.2021.02.004_br0320","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02090763","article-title":"The complexity of ranking simple languages","volume":"23","author":"Huynh","year":"1990","journal-title":"Math. Syst. Theory"},{"issue":"2","key":"10.1016\/j.jcss.2021.02.004_br0330","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s11047-015-9500-y","article-title":"On decidability and closure properties of language classes with respect to bio-operations","volume":"15","author":"Ibarra","year":"2016","journal-title":"Nat. Comput."},{"issue":"5","key":"10.1016\/j.jcss.2021.02.004_br0340","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","article-title":"Nondeterministic space is closed under complementation","volume":"17","author":"Immerman","year":"1988","journal-title":"SIAM J. Comput."},{"author":"Ji","key":"10.1016\/j.jcss.2021.02.004_br0350"},{"key":"10.1016\/j.jcss.2021.02.004_br0360","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.tcs.2016.02.027","article-title":"Closure properties and descriptional complexity of deterministic regular expressions","volume":"627","author":"Losemann","year":"2016","journal-title":"Theor. Comput. Sci."},{"issue":"3\u20134","key":"10.1016\/j.jcss.2021.02.004_br0370","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1002\/rsa.10025","article-title":"A generic approach for the unranking of labeled combinatorial classes","volume":"19","author":"Mart\u00ednez","year":"2001","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/j.jcss.2021.02.004_br0380","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2018.07.002","article-title":"Copyless cost-register automata: structure, expressiveness, and closure properties","volume":"100","author":"Mazowiecki","year":"2019","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.jcss.2021.02.004_br0390","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.dam.2013.10.001","article-title":"Lexicographic ranking and unranking of derangements in cycle notation","volume":"166","author":"Mikawa","year":"2014","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"10.1016\/j.jcss.2021.02.004_br0400","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0020-0190(01)00141-7","article-title":"Ranking and unranking permutations in linear time","volume":"79","author":"Myrvold","year":"2001","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.jcss.2021.02.004_br0410","series-title":"Proceedings of the 20th International Conference on Descriptional Complexity of Formal Systems","first-page":"224","article-title":"Further closure properties of input-driven pushdown automata","volume":"vol. 10952","author":"Okhotin","year":"2018"},{"year":"1967","series-title":"The Theory of Recursive Functions and Effective Computability","author":"Rogers","key":"10.1016\/j.jcss.2021.02.004_br0420"},{"year":"1999","series-title":"Complexity of certificates, heuristics, and counting types, with applications to cryptography and circuit theory","author":"Rothe","key":"10.1016\/j.jcss.2021.02.004_br0430"},{"key":"10.1016\/j.jcss.2021.02.004_br0440","article-title":"Complexity and Structure","volume":"vol. 211","author":"Sch\u00f6ning","year":"1986"},{"issue":"1","key":"10.1016\/j.jcss.2021.02.004_br0450","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01744288","article-title":"P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP","volume":"13","author":"Selman","year":"1979","journal-title":"Math. Syst. Theory"},{"article-title":"Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets","year":"1987","author":"Soare","key":"10.1016\/j.jcss.2021.02.004_br0460"},{"issue":"3","key":"10.1016\/j.jcss.2021.02.004_br0470","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","article-title":"The method of forced enumeration for nondeterministic automata","volume":"26","author":"Szelepcs\u00e9nyi","year":"1988","journal-title":"Acta Inform."},{"key":"10.1016\/j.jcss.2021.02.004_br0480","series-title":"Proceedings of the 8th International Conference on Intelligent Computer Mathematics","first-page":"118","article-title":"Ranking\/unranking of lambda terms with compressed de Bruijn indices","volume":"vol. 9150","author":"Tarau","year":"2015"},{"issue":"11","key":"10.1016\/j.jcss.2021.02.004_br0490","doi-asserted-by":"crossref","first-page":"1388","DOI":"10.1093\/comjnl\/bxs143","article-title":"Ranking and unranking t-ary trees in a Gray-code order","volume":"56","author":"Wu","year":"2013","journal-title":"Comput. J."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000021000192?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000021000192?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T17:07:37Z","timestamp":1672160857000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000021000192"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":49,"alternative-id":["S0022000021000192"],"URL":"https:\/\/doi.org\/10.1016\/j.jcss.2021.02.004","relation":{},"ISSN":["0022-0000"],"issn-type":[{"type":"print","value":"0022-0000"}],"subject":[],"published":{"date-parts":[[2021,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Closure and nonclosure properties of the classes of compressible and rankable sets","name":"articletitle","label":"Article Title"},{"value":"Journal of Computer and System Sciences","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jcss.2021.02.004","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2021 Elsevier Inc. All rights reserved.","name":"copyright","label":"Copyright"}]}}