Logic in Computer Science (LICS 1994)

Paper: Complexity transfer for modal logic (at LICS 1994)

Authors: Edith Hemaspaandra

Abstract

We prove general theorems about the relationship between the complexity of multi-modal logics and the complexity of their uni-modal fragments. Halpern and Moses (1985) show that the complexity of a multi-modal logic without any interaction between the modalities may be higher than the complexity of the individual fragments. We show that under reasonable assumptions the complexity can increase only if the complexity of all the uni-modal fragments is below PSPACE. In addition, we completely characterize what happens if the complexity of all fragments is below PSPACE

BibTeX

  @InProceedings{Hemaspaandra-Complexitytransferf,
    author = 	 {Edith Hemaspaandra},
    title = 	 {Complexity transfer for modal logic},
    booktitle =  {Proceedings of the Ninth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1994},
    year =	 1994,
    editor =	 {Samson Abramsky},
    month =	 {July}, 
    pages =      {164--173},
    location =   {Paris, France}, 
    publisher =	 {IEEE Computer Society Press}
  }