Abstract | ||
---|---|---|
We study the basic modal language extended by an operator dep. If pi are propositional atoms, then dep(p1,…,pn−1;pn) expresses, intuitively, that pn only depends on p1,…,pn−1. The resulting language was baptized ‘modal dependence logic’ by Väänänen in his paper Modal Dependence Logic. The current article compares modal dependence logic with basic modal logic in terms of its model-theoretic and computational properties. We show that modal dependence logic is strictly more expressive than modal logic, but that under special conditions modal dependence logic can be translated into basic modal logic.We show that the complexity of modal dependence logic is NEXP-complete. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1093/logcom/exn102 | J. Log. Comput. |
Keywords | Field | DocType |
paper modal dependence logic,resulting language,basic modal logic,modal logic,current article,computational properties,basic modal language,operator dep,modal dependence logic,propositional atom,computational property | Modal μ-calculus,Discrete mathematics,Normal modal logic,Accessibility relation,Algorithm,Multimodal logic,Linear temporal logic,Modal logic,Mathematics,Dynamic logic (modal logic),Intermediate logic | Journal |
Volume | Issue | ISSN |
19 | 6 | 0955-792X |
Citations | PageRank | References |
23 | 1.29 | 3 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Merlijn Sevenster | 1 | 98 | 13.33 |