English

应用科学学报

• 通信工程 • 上一篇    下一篇

代价和概率时间自动机上概率有界的成本优化可达性

张君华; 黄志球; 曹子宁; 仲晶

  

  1. 南京航空航天大学信息科学与技术学院，南京210016
  • 收稿日期:2008-02-19 修回日期:2008-09-26 出版日期:2009-01-25 发布日期:2009-01-25
  • 通信作者: 张君华

Cost Optimized Reachability with Probability Bound in Priced Probabilistic Timed Automata

ZHANG Jun-hua, HUANG Zhi-qiu, CAO Zi-ning, ZHONG Jing
  

  1. College of Information Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
  • Received:2008-02-19 Revised:2008-09-26 Online:2009-01-25 Published:2009-01-25
  • Contact: ZHANG Jun-hua

PDF

1385

摘要：

着重解决代价和概率时间自动机模型的可达性问题，即满足一定概率要求的最小代价问题. 在该模型中搜索满足概率要求的路径，据此路径构造相应的代价时间自动机，求解此路径的最小代价，从而求得满足概率要求的总的最小代价. 另外，通过扩展代价和概率时间自动机模型，得到多代价和概率时间自动机. 相应的可达性问题，即满足一定概率要求的符合辅助成本约束的主成本最小代价问题，也可类似地得到解决.

关键词: 时间自动机, 概率, 最小代价, 多代价, 可达性

Abstract: This paper solves a reachability problem in priced probabilistic timed automata, which is minimal cost ensuring a probabilistic lower bound. Proper paths that ensure a probability bound in the model are searched. The corresponding priced timed automatons based on these paths are then constructed, and minimal costs obtained. This way, the total minimal cost is naturally obtained. Next, a priced probabilistic timed automaton is extended
to a multi-priced probabilistic timed automaton with multiple price variables. A similar reachability problem in the extended model can also be solved, which is minimal cost on primary cost while ensuring probabilistic lower bound and with respect to secondary cost upper bounds.

Key words: timed automata, probability, minimal cost, multiple prices, reachability

中图分类号: