Concavely-Priced Probabilistic Timed Automata
Concavely-Priced Probabilistic Timed Automata
复制标题
凹价概率时间自动机
DOI：
10.1007/978-3-642-04081-8_28
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Ashutosh Trivedi
中科院分区：
文献类型：
--
作者：
M. Jurdzinski;M. Kwiatkowska;G. Norman;Ashutosh Trivedi
引入了概率时间自动机的一种扩展--凹价概率时间自动机。在本文中，我们考虑的期望可达性，折扣，和平均价格问题的凹价概率时间自动机的任意初始状态。我们证明了这些问题是EXPTIME-完全的概率时间自动机与两个或两个以上的时钟和PTIME-完全的自动机与一个时钟。以往关于概率时间自动机的期望价格问题的研究仅限于线性价格自动机和整数值初始状态的期望可达性。本文利用Jurdzinski和Trivedi提出的边界区域图来分析凹价（非概率）时间自动机的性质。
Concavely-priced probabilistic timed automata, an extension of probabilistic timed automata, are introduced. In this paper we consider expected reachability, discounted, and average price problems for concavely-priced probabilistic timed automata for arbitrary initial states. We prove that these problems are EXPTIME-complete for probabilistic timed automata with two or more clocks and PTIME-complete for automata with one clock. Previous work on expected price problems for probabilistic timed automata was restricted to expected reachability for linearly-priced automata and integer valued initial states. This work uses the boundary region graph introduced by Jurdzinski and Trivedi to analyse properties of concavely-priced (non-probabilistic) timed automata.