Title: Verifying Probabilistic Timed Automata Against Omega-Regular Dense-Time Properties,
Abstract: Probabilistic timed automata (PTAs) are timed automata (TAs) extended with
discrete probability distributions.They serve as a mathematical model for a
wide range of applications that involve both stochastic and timed behaviours.
In this work, we consider the problem of model-checking linear
\emph{dense-time} properties over {PTAs}. In particular, we study linear
dense-time properties that can be encoded by TAs with infinite acceptance
criterion.First, we show that the problem of model-checking PTAs against
deterministic-TA specifications can be solved through a product construction.
Based on the product construction, we prove that the computational complexity
of the problem with deterministic-TA specifications is EXPTIME-complete. Then
we show that when relaxed to general (nondeterministic) TAs, the model-checking
problem becomes undecidable.Our results substantially extend state of the art
with both the dense-time feature and the nondeterminism in TAs.