{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T03:07:27Z","timestamp":1768446447090,"version":"3.49.0"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2013,2,27]],"date-time":"2013-02-27T00:00:00Z","timestamp":1361923200000},"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>An infinite run of a timed automaton is Zeno if it spans only a finite amount\nof time. Such runs are considered unfeasible and hence it is important to\ndetect them, or dually, find runs that are non-Zeno. Over the years important\nimprovements have been obtained in checking reachability properties for timed\nautomata. We show that some of these very efficient optimizations make testing\nfor Zeno runs costly. In particular we show NP-completeness for the\nLU-extrapolation of Behrmann et al. We analyze the source of this complexity in\ndetail and give general conditions on extrapolation operators that guarantee a\n(low) polynomial complexity of Zenoness checking. We propose a slight weakening\nof the LU-extrapolation that satisfies these conditions.<\/jats:p>","DOI":"10.2168\/lmcs-9(1:6)2013","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T13:36:16Z","timestamp":1385732176000},"source":"Crossref","is-referenced-by-count":4,"title":["Coarse abstractions make Zeno behaviours difficult to detect"],"prefix":"10.46298","volume":"Volume 9, Issue 1","author":[{"given":"Fr\u00e9d\u00e9ric","family":"Herbreteau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B","family":"Srivathsan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2013,2,27]]},"reference":[{"key":"748:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/882\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/882\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:58:25Z","timestamp":1681243105000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/882"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,27]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-9(1:6)2013","relation":{"is-same-as":[{"id-type":"arxiv","id":"1106.1850","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1106.1850","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"doi","id":"10.1007\/978-3-642-14295-6_15","asserted-by":"subject"},{"id-type":"doi","id":"10.1007\/s10703-011-0133-1","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2,27]]},"article-number":"882"}}