Name
Abstract | ||
|---|---|---|
We consider the satisfiability problem for modal logic over classes of structures definable by universal first-order formulas with three variables. We exhibit a simple formula for which the problem is undecidable. This improves an earlier result in which nine variables were used. We also show that for classes defined by three-variable, universal Horn formulas the problem is decidable. This subsumes decidability results for many natural modal logics, including T, B, K4, S4, S5. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.4230/LIPIcs.FSTTCS.2011.264 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
modal logic,decidability | Discrete mathematics,Accessibility relation,Normal modal logic,Boolean satisfiability problem,Decidability,Axiom S5,Modal logic,Mathematics,Modal,Undecidable problem | Conference |
Volume | ISSN | Citations |
13 | 1868-8969 | 4 |
PageRank | References | Authors |
0.45 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Emanuel Kieronski | 1 | 114 | 13.85 |
| Jakub Michaliszyn | 2 | 154 | 15.70 |
| Jan Otop | 3 | 43 | 11.44 |