• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Concurrency Theory(CONCUR 2004); 20040831-20040903; London; GB >Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems
【24h】

Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems

机译：确定无限状态概率系统上的概率双相似性

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We prove that probabilistic bisimilarity is decidable over probabilistic extensions of BPA and BPP processes. For normed subclasses of probabilistic BPA and BPP processes we obtain polynomial-time algorithms. Further, we show that probabilistic bisimilarity between probabilistic pushdown automata and finite-state systems is decidable in exponential time. If the number of control states in PDA is bounded by a fixed constant, then the algorithm needs only polynomial time.
机译：我们证明，概率双相似性是决定于BPA和BPP流程的概率扩展的。对于概率BPA和BPP过程的规范子类，我们获得多项式时间算法。此外，我们表明概率下推自动机与有限状态系统之间的概率双相似性可以在指数时间内确定。如果PDA中的控制状态数受固定常数限制，则该算法仅需要多项式时间。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号