资源分类
》 资源 》论文》The Complexity of Model Checking Knowledge and Time

The Complexity of Model Checking Knowledge and Time

2019-09-29 | |  58 |   38 |   0
Abstract We establish the precise complexity of the model checking problem for the main logics of knowledge and time. While this problem was known to be non-elementary for agents with perfect recall, with a number of exponentials that increases with the alternation of knowledge operators, the precise complexity of the problem when the maximum alternation is fixed has been an open problem for twenty years. We close it by establishing improved upper bounds for CTL* with knowledge, and providing matching lower bounds that also apply for epistemic extensions of LTL and CTL

上一篇：Story Ending Prediction by Transferable BERT

下一篇：Worst-Case Optimal Querying of Very Expressive Description Logics withPath Expressions and Succinct Counting

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...