{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:44:56Z","timestamp":1780994696982,"version":"3.54.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>A system of communicating finite state machines is synchronizable if its send\ntrace semantics, i.e.the set of sequences of sendings it can perform, is the\nsame when its communications are FIFO asynchronous and when they are just\nrendez-vous synchronizations. This property was claimed to be decidable in\nseveral conference and journal papers for either mailboxes or peer-to-peer\ncommunications, thanks to a form of small model property. In this paper, we\nshow that this small model property does not hold neither for mailbox\ncommunications, nor for peer-to-peer communications, therefore the decidability\nof synchronizability becomes an open question. We close this question for\npeer-to-peer communications, and we show that synchronizability is actually\nundecidable. We show that synchronizability is decidable if the topology of\ncommunications is an oriented ring. We also show that, in this case,\nsynchronizability implies the absence of unspecified receptions and orphan\nmessages, and the channel-recognizability of the reachability set.<\/jats:p>","DOI":"10.46298\/lmcs-19(4:33)2023","type":"journal-article","created":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T21:25:08Z","timestamp":1703107508000},"source":"Crossref","is-referenced-by-count":2,"title":["Synchronizability of Communicating Finite State Machines is not Decidable"],"prefix":"10.46298","volume":"Volume 19, Issue 4","author":[{"given":"Alain","family":"Finkel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Etienne","family":"Lozes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2023,12,20]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/12724\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/12724\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T21:25:09Z","timestamp":1703107509000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/4764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,20]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(4:33)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"1702.07213v5","asserted-by":"subject"},{"id-type":"arxiv","id":"1702.07213v4","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1702.07213","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1702.07213","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,20]]},"article-number":"4764"}}