Modal dependence logic was introduced very recently by Vaananen. It#R##N#enhances the basic modal language by an operator dep. For propositional#R##N#variables p_1,...,p_n, dep(p_1,...,p_(n-1);p_n) intuitively states that#R##N#the value of p_n only depends on those of p_1,...,p_(n-1). Sevenster (J.#R##N#Logic and Computation, 2009) showed that satisfiability for modal#R##N#dependence logic is complete for nondeterministic exponential time.#R##N##R##N#In this paper we consider fragments of modal dependence logic obtained#R##N#by restricting the set of allowed propositional connectives. We show#R##N#that satisfibility for poor man's dependence logic, the language#R##N#consisting of formulas built from literals and dependence atoms using#R##N#conjunction, necessity and possibility (i.e., disallowing disjunction),#R##N#remains NEXPTIME-complete. If we only allow monotone formulas (without#R##N#negation, but with disjunction), the complexity drops to#R##N#PSPACE-completeness. We also extend Vaananen's language by allowing#R##N#classical disjunction besides dependence disjunction and show that the#R##N#satisfiability problem remains NEXPTIME-complete. If we then disallow#R##N#both negation and dependence disjunction, satistiability is complete for#R##N#the second level of the polynomial hierarchy.#R##N##R##N#In this way we completely classify the computational complexity of the#R##N#satisfiability problem for all restrictions of propositional and#R##N#dependence operators considered by Vaananen and Sevenster.
['Peter Lohmann', 'Heribert Vollmer']
Complexity Results for Modal Dependence Logic