首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Deciding Probabilistic Simulation between Probabilistic Pushdown Automata and Finite-State Systems
  • 本地全文:下载
  • 作者:Hongfei Fu ; Joost-Pieter Katoen
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2011
  • 卷号:13
  • 页码:445-456
  • DOI:10.4230/LIPIcs.FSTTCS.2011.445
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:This paper studies the decidability and computational complexity of checking probabilistic simulation pre-order between probabilistic pushdown automata (pPDA) and (probabilistic)finite-state systems. We show that checking classical and combined probabilistic similarity are EXPTIME-complete in both directions and become polynomial if both the number of control states of the pPDA and the size of the finite-state system are fixed. These results show that checking probabilistic similarity is as hard as checking similarity in the standard, i.e., non-probabilistic setting.
  • 关键词:infinite-state systems; probabilistic simulation; probabilistic pushdown automata
国家哲学社会科学文献中心版权所有