首页 | 本学科首页   官方微博 | 高级检索  
     


Complexity Results of STIT Fragments
Authors:Fran?ois Schwarzentruber
Affiliation:1. ??cole Normale Sup??rieure de Cachan, Cachan, France
Abstract:We provide a Kripke semantics for a STIT logic with the ??next?? operator. As the atemporal group STIT is undecidable and unaxiomatizable, we are interested in strict fragments of atemporal group STIT. First we prove that the satisfiability problem of a formula of the fragment made up of individual coalitions plus the grand coalition is also NEXPTIME-complete. We then generalize this result to a fragment where coalitions are in a given lattice. We also prove that if we restrict the language to nested coalitions the satisfiability problem is NP-complete if the number of agents is fixed and PSPACEcomplete if the number of agents is variable. Finally we embed individual STIT with the ??next?? operator into a fragment of atemporal group STIT.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号