资源分类
》 资源 》论文》The Complexity of One-Agent Refinement Modal Logic

The Complexity of One-Agent Refinement Modal Logic

2019-11-11 | |  49 |   39 |   0

Abstract We investigate the complexity of satisfiability for one-agent refinement modal logic (RML), an extension of basic modal logic (ML) obtained by adding refinement quantifiers on structures. RML is known to have the same expressiveness as ML, but the translation of RML into ML is of non-elementary complexity, and RML is at least doubly exponentially more succinct than ML. In this paper we show that RML-satisfiability is ‘only’ singly exponentially harder than ML-satisfiability, the latter being a well-known PSPACE-complete problem.

上一篇：An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning (Extended Abstract)1

下一篇：An Introduction to String Re-Writing Kernel

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

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

  • Rating-Boosted La...

    The performance of a recommendation system reli...