Logic in Computer Science (LICS 2000)

Paper: Back and Forth between Guarded and Modal Logics (at LICS 2000)

Authors: Erich Graedel Colin Hirsch Martin Otto

Abstract

We propose a second-order extension for the guarded fragment showing that several canonical extensions are in fact equivalent. Then we ask the question in how far results from the modal world can be brought into the world of guarded logics. We give a transformation from first-order structures to Kripke type transition systems. This is used here to transform a theorem due to Janin and Walukiewicz about the expressive completeness of fixed-point logic in the context of bisimulation invariance.

BibTeX

  @InProceedings{GraedelHirschOtto-BackandForthbetween,
    author = 	 {Erich Graedel and Colin Hirsch and Martin Otto},
    title = 	 {Back and Forth between Guarded and Modal Logics},
    booktitle =  {Proceedings of the Fifteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2000},
    year =	 2000,
    editor =	 {Martin Abadi},
    month =	 {June}, 
    pages =      {217--228},
    location =   {Santa Barbara, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }