{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:42:28Z","timestamp":1777596148932,"version":"3.51.4"},"reference-count":43,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2014,11,12]],"date-time":"2014-11-12T00:00:00Z","timestamp":1415750400000},"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":[[2016,9]]},"abstract":"<jats:p>A well-known result by Palamidessi tells us that \u03c0<jats:sub>mix<\/jats:sub>(the \u03c0-calculus with mixed choice) is more expressive than \u03c0<jats:sub>sep<\/jats:sub>(its subset with only separate choice). The proof of this result analyses their different expressive power concerning leader election in symmetric networks. Later on, Gorla offered an arguably simpler proof that, instead of leader election in symmetric networks, employed the reducibility of \u2018incestual\u2019 processes (mixed choices that include both enabled senders and receivers for the same channel) when running two copies in parallel. In both proofs, the role of<jats:italic>breaking (initial) symmetries<\/jats:italic>is more or less apparent. In this paper, we shed more light on this role by re-proving the above result \u2013 based on a proper formalization of what it means to break symmetries \u2013 without referring to another problem domain like leader election.<\/jats:p><jats:p>Both Palamidessi and Gorla rephrased their results by stating that there is no uniform and reasonable encoding from \u03c0<jats:sub>mix<\/jats:sub>into \u03c0<jats:sub>sep<\/jats:sub>. We indicate how their proofs can be adapted and exhibit the consequences of varying notions of uniformity and reasonableness. In each case, the ability to break initial symmetries turns out to be essential. Moreover, by abandoning the uniformity criterion, we show that there indeed is a reasonable encoding. We emphasize its underlying principle, which highlights the difference between breaking symmetries locally instead of globally.<\/jats:p>","DOI":"10.1017\/s0960129514000346","type":"journal-article","created":{"date-parts":[[2014,11,12]],"date-time":"2014-11-12T08:36:29Z","timestamp":1415781389000},"page":"1054-1106","source":"Crossref","is-referenced-by-count":5,"title":["Breaking symmetries"],"prefix":"10.1017","volume":"26","author":[{"given":"KIRSTIN","family":"PETERS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"UWE","family":"NESTMANN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,11,12]]},"reference":[{"key":"S0960129514000346_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050018"},{"key":"S0960129514000346_ref9","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2823"},{"key":"S0960129514000346_ref41","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57208-2_6"},{"key":"S0960129514000346_ref31","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.41.10"},{"key":"S0960129514000346_ref20","first-page":"475","article-title":"A distributed protocol for channel-based communication with choice.","volume":"12","author":"Knabe","year":"1993","journal-title":"Computers and Artificial Intelligence"},{"key":"S0960129514000346_ref5","unstructured":"Boudol G. (1992) Asynchrony and the \u03c0-calculus (note). Note, INRIA."},{"key":"S0960129514000346_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263584"},{"key":"S0960129514000346_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_97"},{"key":"S0960129514000346_ref36","volume-title":"The \u03c0-Calculus: A Theory of Mobile Processes","author":"Sangiorgi","year":"2001"},{"key":"S0960129514000346_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.05.002"},{"key":"S0960129514000346_ref35","unstructured":"Priami C. (1996) Enhanced Operational Semantics for Concurrency, Ph.D. thesis, Universit\u00e0 di Pisa-Genova-Udine."},{"key":"S0960129514000346_ref28","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2868"},{"key":"S0960129514000346_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.05.001"},{"key":"S0960129514000346_ref42","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482830-9\/50019-9"},{"key":"S0960129514000346_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/11817949_4"},{"key":"S0960129514000346_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0057019"},{"key":"S0960129514000346_ref39","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0084811"},{"key":"S0960129514000346_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55719-9_114"},{"key":"S0960129514000346_ref19","first-page":"13","volume-title":"Proceedings of PODC","author":"Johnson","year":"1985"},{"key":"S0960129514000346_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/357094.357101"},{"key":"S0960129514000346_ref29","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129503004043"},{"key":"S0960129514000346_ref33","doi-asserted-by":"crossref","unstructured":"Peters K and Nestmann U. (2012b) Is it a \u2018Good\u2019 encoding of mixed choice? Technical Report, TU Berlin, Germany. http:\/\/arxiv.org\/corr\/home.","DOI":"10.1007\/978-3-642-28729-9_14"},{"key":"S0960129514000346_ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.09.001"},{"key":"S0960129514000346_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54430-5_85"},{"key":"S0960129514000346_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/357073.357077"},{"key":"S0960129514000346_ref8","first-page":"251","volume-title":"SIGPLAN-SIGACT","author":"Bugliesi","year":"2007"},{"key":"S0960129514000346_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050124"},{"key":"S0960129514000346_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/69624.357208"},{"key":"S0960129514000346_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/359576.359585"},{"key":"S0960129514000346_ref40","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90126-5"},{"key":"S0960129514000346_ref10","first-page":"70","article-title":"On the expressive power of polyadic synchronisation in \u03c0-calculus.","volume":"10","author":"Carbone","year":"2003","journal-title":"Nordic Journal of Computing"},{"key":"S0960129514000346_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.04.011"},{"key":"S0960129514000346_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00040-9"},{"key":"S0960129514000346_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90008-4"},{"key":"S0960129514000346_ref38","first-page":"198","volume-title":"Proceedings of STOC","author":"Shapiro","year":"1991"},{"key":"S0960129514000346_ref14","doi-asserted-by":"crossref","unstructured":"Gorla D. (2008b) Towards a unified approach to encodability and separation results for process calculi, Technical Report, Dip. di Informatica, Univ. di Roma \u2018La Sapienza\u2019, 2008. (An extended abstract appeared in the Proceedings of CONCUR'08. Springer Lecture Notes in Computer Science 5201 492\u2013507.)","DOI":"10.1007\/978-3-540-85361-9_38"},{"key":"S0960129514000346_ref34","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.64.7"},{"key":"S0960129514000346_ref23","doi-asserted-by":"crossref","unstructured":"Lipton R. , Snyder L. and Zalcstein Y. (1974) A comparative study of models of parallel computation. In: 15th Annual Symposium on Switching and Automata Theory, New Orleans 145\u2013155.","DOI":"10.1109\/SWAT.1974.2"},{"key":"S0960129514000346_ref26","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2822"},{"key":"S0960129514000346_ref17","first-page":"537","volume-title":"IFIP Conference Proceedings","author":"Herescu","year":"2002"},{"key":"S0960129514000346_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28729-9_14"},{"key":"S0960129514000346_ref37","doi-asserted-by":"publisher","DOI":"10.1145\/72551.72555"},{"key":"S0960129514000346_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.11.011"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129514000346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T08:11:04Z","timestamp":1566029464000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129514000346\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,12]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["S0960129514000346"],"URL":"https:\/\/doi.org\/10.1017\/s0960129514000346","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,12]]}}}