• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Quantitative Automata under Probabilistic Semantics
【24h】

Quantitative Automata under Probabilistic Semantics

机译：概率语义学下的定量自动机

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor counters and nested weighted automata are equivalent. We study for the first time such quantitative automata under probabilistic semantics. We show that several problems that are undecidable for the classical questions of emptiness and universality become decidable under the probabilistic semantics. We present a complete picture of decidability for such automata, and even an almost-complete picture of computational complexity, for the probabilistic questions we consider.
机译：具有监视计数器的自动机（其中过渡不取决于计数器值）和嵌套加权自动机是两个表达性自动机理论框架，用于定量属性。对于经过广泛研究的定量函数类，我们确定带有监视器计数器的自动机和嵌套加权自动机是等效的。我们首次研究了概率语义下的这种定量自动机。我们表明，在概率语义下，对于空虚和普遍性的经典问题无法决定的几个问题变得可以决定。对于我们考虑的概率问题，我们提供了此类自动机可判定性的完整图片，甚至是计算复杂度的几乎完整图片。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号