{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T21:27:18Z","timestamp":1790717238884,"version":"4.1.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2008,9,26]],"date-time":"2008-09-26T00:00:00Z","timestamp":1222387200000},"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>Probabilistic timed automata are an extension of timed automata with discrete\nprobability distributions. We consider model-checking algorithms for the\nsubclasses of probabilistic timed automata which have one or two clocks.\nFirstly, we show that PCTL probabilistic model-checking problems (such as\ndetermining whether a set of target states can be reached with probability at\nleast 0.99 regardless of how nondeterminism is resolved) are PTIME-complete for\none-clock probabilistic timed automata, and are EXPTIME-complete for\nprobabilistic timed automata with two clocks. Secondly, we show that, for\none-clock probabilistic timed automata, the model-checking problem for the\nprobabilistic timed temporal logic PCTL is EXPTIME-complete. However, the\nmodel-checking problem for the subclass of PCTL which does not permit both\npunctual timing bounds, which require the occurrence of an event at an exact\ntime point, and comparisons with probability bounds other than 0 or 1, is\nPTIME-complete for one-clock probabilistic timed automata.<\/jats:p>","DOI":"10.2168\/lmcs-4(3:12)2008","type":"journal-article","created":{"date-parts":[[2009,1,9]],"date-time":"2009-01-09T10:23:40Z","timestamp":1231496620000},"source":"Crossref","is-referenced-by-count":25,"title":["Model Checking Probabilistic Timed Automata with One or Two Clocks"],"prefix":"10.46298","volume":"Volume 4, Issue 3","author":[{"given":"Marcin","family":"Jurdzinski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francois","family":"Laroussinie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeremy","family":"Sproston","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2008,9,26]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/988\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/988\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:00:46Z","timestamp":1681243246000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/988"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9,26]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-4(3:12)2008","relation":{"is-same-as":[{"id-type":"arxiv","id":"0809.0060","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.0809.0060","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9,26]]},"article-number":"988"}}