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 等数据库收录! |
|