{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T02:06:23Z","timestamp":1790647583183,"version":"4.1.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We study timed systems in which some timing features are unknown parameters.\nParametric timed automata (PTAs) are a classical formalism for such systems but\nfor which most interesting problems are undecidable. Notably, the parametric\nreachability emptiness problem, i.e., the emptiness of the parameter valuations\nset allowing to reach some given discrete state, is undecidable.\nLower-bound\/upper-bound parametric timed automata (L\/U-PTAs) achieve\ndecidability for reachability properties by enforcing a separation of\nparameters used as upper bounds in the automaton constraints, and those used as\nlower bounds.\n  In this paper, we first study reachability. We exhibit a subclass of PTAs\n(namely integer-points PTAs) with bounded rational-valued parameters for which\nthe parametric reachability emptiness problem is decidable. Using this class,\nwe present further results improving the boundary between decidability and\nundecidability for PTAs and their subclasses such as L\/U-PTAs.\n  We then study liveness. We prove that:\n  (1) deciding the existence of at least one parameter valuation for which\nthere exists an infinite run in an L\/U-PTA is PSpace-complete;\n  (2) the existence of a parameter valuation such that the system has a\ndeadlock is however undecidable;\n  (3) the problem of the existence of a valuation for which a run remains in a\ngiven set of locations exhibits a very thin border between decidability and\nundecidability.<\/jats:p>","DOI":"10.46298\/lmcs-18(1:31)2022","type":"journal-article","created":{"date-parts":[[2022,2,10]],"date-time":"2022-02-10T14:42:16Z","timestamp":1644504136000},"source":"Crossref","is-referenced-by-count":4,"title":["Reachability and liveness in parametric timed automata"],"prefix":"10.46298","volume":"Volume 18, Issue 1","author":[{"given":"\u00c9tienne","family":"Andr\u00e9","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Didier","family":"Lime","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Olivier H.","family":"Roux","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2022,2,9]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9070\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9070\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:17:45Z","timestamp":1687292265000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/6312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(1:31)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"2004.09171v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2004.09171v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2004.09171","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2004.09171","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,9]]},"article-number":"6312"}}