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

摘要

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