Computability and Complexity

Maarten de Rijke, Yde VenemaCambridge 2001 · DOI · OpenAlex

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...

Figure