Modd checking probabilistic timed automata with one or two clocks
Jurdzinski, Marcin, Laroussinie, Francois and Sproston, Jeremy (2007) Modd checking probabilistic timed automata with one or two clocks. In: 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Braga, PORTUGAL, MAR 24-APR 01, 2007. Published in: Tools and Algorithms for the Construction and Analysis of Systems, Proceedings, 4424 pp. 170-184.Full text not available from this repository.
Probabilistic timed automata are an extension of timed automata with discrete probability distributions. We consider model-checking algorithms for the subclasses of probabilistic timed automata which have one or two clocks. Firstly, we show that PCTL probabilistic model-checking problems (such as determining whether it set of target states can be reached with probability at least 0.99 regardless of how nondeterminism is resolved) are PTIME-complete for one clock probabilistic timed automata, and are EXPTIME-complete for probabilistic timed automata with two clocks. Secondly, we show that the model-checking problem for the probabilistic timed temporal logic PTCTL is EXPTIME-complete for one clock probabilistic timed automata. However, the corresponding model-checking problem for the subclass of PTCTL which does not permit both (1) punctual timing bounds, which require the occurrence of an event at an exact time point, and (2) comparisons with probability bounds other than 0 or 1, is PTIME-complete.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||LECTURE NOTES IN COMPUTER SCIENCE|
|Journal or Publication Title:||Tools and Algorithms for the Construction and Analysis of Systems, Proceedings|
|Editor:||Grumberg, O and Huth, M|
|Number of Pages:||15|
|Page Range:||pp. 170-184|
|Title of Event:||13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems|
|Location of Event:||Braga, PORTUGAL|
|Date(s) of Event:||MAR 24-APR 01, 2007|
Actions (login required)