{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:03Z","timestamp":1750220943607,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T00:00:00Z","timestamp":1556236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/M023974\/1"],"award-info":[{"award-number":["EP\/M023974\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"EPSRC Doctoral Training"},{"name":"Royal Society Leverhulme Trust Senior Research Fellowship","award":["LT170023"],"award-info":[{"award-number":["LT170023"]}]},{"name":"Merton College Research Fund"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            We prove that the observational equivalence problem for a finitary fragment of the programming langauge ML is recursively equivalent to the reachability problem for\n            <jats:italic>extended branching vector addition systems with states<\/jats:italic>\n            (EBVASS). This result has two natural and independent parts. We first prove that the observational equivalence problem is equivalent to the emptiness problem for a new class of class memory automata equipped with a visibly pushdown stack, called\n            <jats:italic>Visibly Pushdown Class Memory Automata<\/jats:italic>\n            (VPCMA). Our proof uses the fully abstract game semantics of the language. We then prove that the VPCMA emptiness problem is equivalent to the reachability problem for EBVASS. The results of this article complete our programme to give an automata classification of the ML types with respect to the observational equivalence problem for closed terms.\n          <\/jats:p>","DOI":"10.1145\/3310338","type":"journal-article","created":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T17:12:14Z","timestamp":1556557934000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["ML, Visibly Pushdown Class Memory Automata, and Extended Branching Vector Addition Systems with States"],"prefix":"10.1145","volume":"41","author":[{"given":"Conrad","family":"Cotton-Barratt","sequence":"first","affiliation":[{"name":"Jump Trading London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej S.","family":"Murawski","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.-H. Luke","family":"Ong","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2930"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(05)80398-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/647847.736902"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007390"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90067-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2391495.2391506"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.10.009"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46678-0_16"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-15579-1_14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_12"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018438.1021843"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646253.758834"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1630034"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00039-0"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027223.2027238"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2917"},{"key":"e_1_2_1_19_1","volume-title":"data tree automata and branching vector addition systems. Logic. Methods Comput. Sci. 12, 2","author":"Jacquemard Florent","year":"2016","unstructured":"Florent Jacquemard, Luc Segoufin, and Jer\u00e9mie Dimino. 2016. FO2(&lt;, +1, &tilde;) on data trees, data tree automata and branching vector addition systems. Logic. Methods Comput. Sci. 12, 2 (2016)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2733375"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.036"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_74"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24953-7_30"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Foundations of Software Science and Computation Structures (FOSSAC\u201909)","volume":"5504","author":"Andrzej","unstructured":"Andrzej S. Murawski and Nikos Tzevelekos. 2009. Full abstraction for reduced ML. In Proceedings of the International Conference on Foundations of Software Science and Computation Structures (FOSSAC\u201909). Lecture Notes in Computer Science, Vol. 5504. Springer, 32--47."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1987211.1987233"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_30"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645683.758050"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/309656.309671"},{"key":"e_1_2_1_29_1","unstructured":"John C. Reynolds. 1981. The essence of algol. In Algorithmic Languages. North Holland 345--372."}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3310338","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3310338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:37Z","timestamp":1750204417000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3310338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,26]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3310338"],"URL":"https:\/\/doi.org\/10.1145\/3310338","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2019,4,26]]},"assertion":[{"value":"2017-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}