{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T20:54:38Z","timestamp":1760043278969,"version":"3.37.3"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T00:00:00Z","timestamp":1519862400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100005736","name":"Universit\u00e9 Paris Diderot","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005736","id-type":"DOI","asserted-by":"publisher"}]},{"name":"INRIA-EPFL"},{"DOI":"10.13039\/501100001703","name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001703","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s00607-018-0596-7","type":"journal-article","created":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T03:00:41Z","timestamp":1519873241000},"page":"1227-1240","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the complexity of linearizability"],"prefix":"10.1007","volume":"101","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2691-3337","authenticated-orcid":false,"given":"Jad","family":"Hamza","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,1]]},"reference":[{"issue":"1\u20132","key":"596_CR1","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1006\/inco.1999.2847","volume":"160","author":"R Alur","year":"2000","unstructured":"Alur R, McMillan KL, Peled D (2000) Model-checking of correctness conditions for concurrent objects. Inf Comput 160(1\u20132):167\u2013188","journal-title":"Inf Comput"},{"key":"596_CR2","doi-asserted-by":"crossref","unstructured":"Bouajjani A, Emmi M, Enea C, Hamza J (2013) Verifying concurrent programs against sequential specifications. In: ESOP\u201913. LNCS, vol 7792. Springer, pp 290\u2013309","DOI":"10.1007\/978-3-642-37036-6_17"},{"key":"596_CR3","doi-asserted-by":"publisher","unstructured":"Burckhardt S, Dern C, Musuvathi M, Tan R (2010) Line-up: a complete and automatic linearizability checker. In: Proceedings of the 2010 ACM SIGPLAN conference on programming language design and implementation, PLDI\u201910. ACM, New York, pp 330\u2013340. \n                    https:\/\/doi.org\/10.1145\/1806596.1806634","DOI":"10.1145\/1806596.1806634"},{"key":"596_CR4","doi-asserted-by":"crossref","unstructured":"Elmas T, Qadeer S, Sezgin A, Subasi O, Ta\u015f\u0131ran S (2010) Simplifying linearizability proofs with reduction and abstraction. In: TACAS\u201910: Proceedings of the 16th international conference on tools and algorithms for the construction and analysis of systems. LNCS, vol 6015. Springer, pp 296\u2013311","DOI":"10.1007\/978-3-642-12002-2_25"},{"issue":"51\u201352","key":"596_CR5","doi-asserted-by":"publisher","first-page":"4379","DOI":"10.1016\/j.tcs.2010.09.021","volume":"411","author":"I Filipovic","year":"2010","unstructured":"Filipovic I, O\u2019Hearn PW, Rinetzky N, Yang H (2010) Abstraction for concurrent objects. Theor Comput Sci 411(51\u201352):4379\u20134398","journal-title":"Theor Comput Sci"},{"key":"596_CR6","doi-asserted-by":"crossref","unstructured":"F\u00fcrer M (1980) The complexity of the inequivalence problem for regular expressions with intersection. In: Proceedings of the 7th colloquium on automata, languages and programming. Springer, London, pp 234\u2013245. \n                    http:\/\/dl.acm.org\/citation.cfm?id=646234.682559","DOI":"10.1007\/3-540-10003-2_74"},{"issue":"4","key":"596_CR7","doi-asserted-by":"publisher","first-page":"1208","DOI":"10.1137\/S0097539794279614","volume":"26","author":"PB Gibbons","year":"1997","unstructured":"Gibbons PB, Korach E (1997) Testing shared memories. SIAM J Comput 26(4):1208\u20131244","journal-title":"SIAM J Comput"},{"issue":"3","key":"596_CR8","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M Herlihy","year":"1990","unstructured":"Herlihy M, Wing JM (1990) Linearizability: a correctness condition for concurrent objects. ACM Trans Program Lang Syst 12(3):463\u2013492","journal-title":"ACM Trans Program Lang Syst"},{"key":"596_CR9","unstructured":"Hunt H (1973) The equivalence problem for regular expressions with intersection is not polynomial in tape. Department of Computer Science: technical report, Cornell University, Department of Computer Science. \n                    http:\/\/books.google.fr\/books?id=52j6HAAACAAJ"},{"issue":"2","key":"596_CR10","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1006\/inco.1994.1098","volume":"115","author":"AJ Mayer","year":"1994","unstructured":"Mayer AJ, Stockmeyer LJ (1994) The complexity of word problems\u2014this time with interleaving. Inf Comput 115(2):293\u2013311. \n                    https:\/\/doi.org\/10.1006\/inco.1994.1098","journal-title":"Inf Comput"},{"key":"596_CR11","unstructured":"Rajamani SK, Walker D (eds) (2015) Proceedings of the 42nd annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL 2015, Mumbai, India, January 15\u201317, 2015. ACM. \n                    http:\/\/dl.acm.org\/citation.cfm?id=2676726"},{"key":"596_CR12","unstructured":"Vafeiadis V (2010) Automatically proving linearizability. In: CAV\u201910. LNCS, vol 6174, pp 450\u2013464"},{"key":"596_CR13","doi-asserted-by":"crossref","unstructured":"Vechev MT, Yahav E, Yorsh, G (2009) Experience with model checking linearizability. In: SPIN\u201909: Proceedings of the 16th international SPIN workshop on model checking software. LNCS, vol 5578. Springer, pp 261\u2013278","DOI":"10.1007\/978-3-642-02652-2_21"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-018-0596-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00607-018-0596-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-018-0596-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,22]],"date-time":"2019-09-22T05:41:07Z","timestamp":1569130867000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00607-018-0596-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,1]]},"references-count":13,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["596"],"URL":"https:\/\/doi.org\/10.1007\/s00607-018-0596-7","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"type":"print","value":"0010-485X"},{"type":"electronic","value":"1436-5057"}],"subject":[],"published":{"date-parts":[[2018,3,1]]},"assertion":[{"value":"8 May 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}