The Library
Modd checking probabilistic timed automata with one or two clocks
Tools
Jurdzinski, Marcin, Laroussinie, Francois and Sproston, Jeremy (2007) Modd checking probabilistic timed automata with one or two clocks. In: Grumberg, O. and Huth, M., (eds.) Tools and Algorithms for the Construction and Analysis of Systems : 13th International Conference, TACAS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007 Braga, Portugal, March 24 - April 1, 2007. Proceed. Lecture Notes in Computer Science, Volume 4424 . Springer Verlag, pp. 170-184. ISBN 9783540712084
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
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: | Book Item | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Journal or Publication Title: | Tools and Algorithms for the Construction and Analysis of Systems, Proceedings | ||||
Publisher: | Springer Verlag | ||||
ISBN: | 9783540712084 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Tools and Algorithms for the Construction and Analysis of Systems : 13th International Conference, TACAS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007 Braga, Portugal, March 24 - April 1, 2007. Proceed | ||||
Editor: | Grumberg, O. and Huth, M. | ||||
Official Date: | 2007 | ||||
Dates: |
|
||||
Volume: | Volume 4424 | ||||
Number of Pages: | 15 | ||||
Page Range: | pp. 170-184 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Conference Paper Type: | Paper | ||||
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: | 24 Mar - 1 Apr 2007 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |