Computability and Complexity
Lists
Only you see this
Abstract
In this chapter we investigate the computability and complexity of normal modal logics. In particular, we examine the computability of satisfiability problems (given a modal formula ø and a class of models M, is it computable whether ø is M-satisfiable?) and validity problems (given a modal formula ø and a class of models M, is it computable whether ø is valid on M?). When the answer is ‘yes’, we probe further: how complex is the problem — in particular, what resources of time (that is, computation steps) or space (that is, memory) are needed to carry out the required computations? When the answer is ‘no’, we pose a similar question: how uncomputable is the problem? There are vast differences in the complexities of modal satisfiability problems: some are no worse than the satisfiability problem for propositional calculus, while others are highly undecidable.
BibTeX
@inproceedings{rijke2001computability,
author = {Maarten de Rijke and Yde Venema},
title = {{Computability and Complexity}},
booktitle = {Cambridge},
year = {2001},
doi = {10.1017/cbo9781107050884.007},
}Loading related content...