Paper: Existential Second-Order Logic over Strings (at LICS 1998)

Authors: Thomas Eiter Georg Gottlob Yuri Gurevich

Abstract

Existential second-order logic (ESO) and monadic second-order logic (MSO) have attracted much interest in logic and computer science. ESO is a much more expressive logic over word structures than MSO. However, little was known about the relationship between MSO and syntactic fragments of ESO. We shed light on this issue by completely characterizing this relationship for the prefix classes of ESO over strings, (i.e., finite word structures). Moreover, we determine the complexity of model checking over strings, for all ESO-prefix classes. We also give a precise characterization of those ESO-prefix classes which are equivalent to MSO over strings, and of the ESO-prefix classes which are closed under complementation on strings

BibTeX

  @InProceedings{EiterGottlobGurevic-ExistentialSecondOr,
    author = 	 {Thomas Eiter and Georg Gottlob and Yuri Gurevich},
    title = 	 {Existential Second-Order Logic over Strings},
    booktitle =  {Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1998)},
    year =	 {1998},
    month =	 {June}, 
    pages =      {16--27},
    location =   {Indianapolis, IN, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }