Name
Abstract | ||
|---|---|---|
We consider the sabotage modal logic SML which was suggested by van Benthem. SML is the modal logic equipped with a 'transition-deleting' modality and hence a modal logic over changing models. It was shown that the problem of uniform model checking for this logic is PSPACE-complete. In this paper we show that, on the other hand, the formula complexity and the program complexity are linear, resp., polynomial time. Further we show that SML lacks nice model-theoretic properties such as bisimulation invariance, the tree model property, and the finite model property. Finally we show that the satisfiability problem for SML is undecidable. Therefore SML seems to be more related to FO than to usual modal logic. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-24597-1_26 | LECTURE NOTES IN COMPUTER SCIENCE |
Keywords | Field | DocType |
satisfiability,modal logic,polynomial time,model checking | Modal μ-calculus,Discrete mathematics,Finite model property,Accessibility relation,Normal modal logic,Computer science,Multimodal logic,Linear temporal logic,Modal logic,Dynamic logic (modal logic) | Conference |
Volume | ISSN | Citations |
2914 | 0302-9743 | 22 |
PageRank | References | Authors |
1.05 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christof Löding | 1 | 326 | 28.57 |
| Philipp Rohde | 2 | 44 | 4.73 |
| RWTH Aachen | 3 | 102 | 16.14 |