{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T19:52:28Z","timestamp":1762458748983},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2009,6,1]],"date-time":"2009-06-01T00:00:00Z","timestamp":1243814400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p>The investigation into the foundational aspects of linguistic mechanisms for programming long-running transactions (such as the<jats:italic>scope<\/jats:italic>operator of WS-BPEL) has recently renewed the interest in process algebraic operators that, due to the occurrence of a failure,<jats:italic>interrupt<\/jats:italic>the execution of one process, replacing it with another one called the<jats:italic>failure handler<\/jats:italic>. We investigate the decidability of termination problems for two simple fragments of CCS (one with recursion and one with replication) extended with one of two such operators, the<jats:italic>interrupt<\/jats:italic>operator of CSP and the<jats:italic>try-catch<\/jats:italic>operator for exception handling. More precisely, we consider the existential termination problem (existence of one terminated computation) and the universal termination problem (all computations terminate). We prove that, as far as the decidability of the considered problems is concerned, under replication there is no difference between interrupt and try-catch (universal termination is decidable while existential termination is not), while under recursion this is not the case (existential termination is undecidable while universal termination is decidable only for interrupt). As a consequence of our undecidability results, we show the existence of an expressiveness gap between a fragment of CCS and its extension with either the interrupt or the try-catch operator.<\/jats:p>","DOI":"10.1017\/s0960129509007683","type":"journal-article","created":{"date-parts":[[2009,5,6]],"date-time":"2009-05-06T10:07:58Z","timestamp":1241604478000},"page":"565-599","source":"Crossref","is-referenced-by-count":19,"title":["On the expressive power of process interruption and compensation"],"prefix":"10.1017","volume":"19","author":[{"given":"MARIO","family":"BRAVETTI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GIANLUIGI","family":"ZAVATTARO","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,6,1]]},"reference":[{"key":"S0960129509007683_ref29","unstructured":"W3C (2004) WS-CDL: Web Services Choreography Description Language. Technical report, W3C."},{"key":"S0960129509007683_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78739-6_21"},{"key":"S0960129509007683_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(09)70156-9"},{"key":"S0960129509007683_ref24","unstructured":"OASIS (2003) WS-BPEL: Web Services Business Process Execution Language Version 2.0. Technical report, OASIS, 2003."},{"key":"S0960129509007683_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71316-6_4"},{"key":"S0960129509007683_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31982-5_18"},{"key":"S0960129509007683_ref17","first-page":"210","article-title":"Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture","volume":"95","author":"Kruskal","year":"1960","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0960129509007683_ref15","first-page":"236","article-title":"Ordering by divisibility in abstract algebras","volume":"2","author":"Higman","year":"1952","journal-title":"Proc. London Math. Soc."},{"key":"S0960129509007683_ref14","first-page":"190","volume-title":"ACSD'08: Proceedings of 8th International Conference on Application of Concurrency to System Design","author":"Guidi","year":"2008"},{"key":"S0960129509007683_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00102-X"},{"key":"S0960129509007683_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/11423348_8"},{"key":"S0960129509007683_ref26","doi-asserted-by":"publisher","DOI":"10.1145\/321160.321170"},{"key":"S0960129509007683_ref8","doi-asserted-by":"crossref","unstructured":"Busi N. , Gabbrielli M. and Zavattaro G. (2009) On the Expressive Power of Recursion, Replication and Iteration in Process Calculi. Mathematical Structures in Computer Science (to appear). (This is an extended version of Busi et al. (2003).)","DOI":"10.1017\/S096012950999017X"},{"key":"S0960129509007683_ref6","first-page":"209","volume-title":"POPL 2005: Proceedings of the 32nd Symposium on Principles of Programming Languages","author":"Bruni","year":"2005"},{"key":"S0960129509007683_ref5","first-page":"563","volume-title":"TCS 2004: IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science","author":"Bruni","year":"2004"},{"key":"S0960129509007683_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/11841197_3"},{"key":"S0960129509007683_ref1","volume-title":"Process algebra (equational theories of communicating processes)","author":"Baeten","year":"2008"},{"key":"S0960129509007683_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_12"},{"key":"S0960129509007683_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24634-3_9"},{"key":"S0960129509007683_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017157"},{"key":"S0960129509007683_ref22","unstructured":"Minsky M. L. (1967) Computation: finite and infinite machines, Prentice-Hall."},{"key":"S0960129509007683_ref2","unstructured":"Baeten J. C. M. and Bergstra J. A. (2000) Mode transfer in process algebra. Report CSR 00-01, Technische Universiteit Eindhoven. (This paper is an expanded and revised version of: Bergstra, J. (2000) A mode transfer operator in process algebra, Report P8808, Programming Research Group, University of Amsterdam, which is available at http:\/\/alexandria.tue.nl\/extra1\/wskrap\/publichtml\/200010731.pdf.)"},{"key":"S0960129509007683_ref11","first-page":"245","article-title":"Decidability Issues for Petri Nets-a Survey","volume":"52","author":"Esparza","year":"1994","journal-title":"Bulletin of the European Association for TCS"},{"key":"S0960129509007683_ref25","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129503004043"},{"key":"S0960129509007683_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s10270-006-0012-1"},{"key":"S0960129509007683_ref20","unstructured":"Milner R. (1989) Communication and Concurrency, Prentice-Hall."},{"key":"S0960129509007683_ref16","doi-asserted-by":"crossref","unstructured":"Hoare C. A. R. (1985) Communicating Sequential Processes, Prentice-Hall.","DOI":"10.1007\/978-3-642-82921-5_4"},{"key":"S0960129509007683_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90008-4"},{"key":"S0960129509007683_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39958-2_9"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129509007683","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T01:33:25Z","timestamp":1684978405000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129509007683\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["S0960129509007683"],"URL":"https:\/\/doi.org\/10.1017\/s0960129509007683","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}