{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T19:58:57Z","timestamp":1762459137581,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,9,27]],"date-time":"2012-09-27T00:00:00Z","timestamp":1348704000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The reachability analysis of recursive programs that communicate\nasynchronously over reliable FIFO channels calls for restrictions to ensure\ndecidability. Our first result characterizes communication topologies with a\ndecidable reachability problem restricted to eager runs (i.e., runs where\nmessages are either received immediately after being sent, or never received).\nThe problem is EXPTIME-complete in the decidable case. The second result is a\ndoubly exponential time algorithm for bounded context analysis in this setting,\ntogether with a matching lower bound. Both results extend and improve previous\nwork from La Torre et al.<\/jats:p>","DOI":"10.2168\/lmcs-8(3:23)2012","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T08:17:46Z","timestamp":1385713066000},"source":"Crossref","is-referenced-by-count":11,"title":["Reachability Analysis of Communicating Pushdown Systems"],"prefix":"10.46298","volume":"Volume 8, Issue 3","author":[{"given":"Alexander","family":"Heussner","sequence":"first","affiliation":[]},{"given":"J\u00e9r\u00f4me","family":"Leroux","sequence":"additional","affiliation":[]},{"given":"Anca","family":"Muscholl","sequence":"additional","affiliation":[]},{"given":"Gr\u00e9goire","family":"Sutre","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,9,27]]},"reference":[{"key":"558:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/921\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/921\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:59:05Z","timestamp":1681243145000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/921"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,27]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(3:23)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1209.0359","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1209.0359","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,9,27]]},"article-number":"921"}}