Logic in Computer Science (LICS 1988)

Paper: 0-1 laws and decision problems for fragments of second-order logic (at LICS 1988)

Authors: Phokion G. Kolaitis Moshe Y. Vardi

Abstract

Fragments of existential second-order logic are investigated in which the patterns of first order quantifiers are restricted. The focus is on the class ∑₁¹ (Ackermann) of existential second-order sentences in which the first-order part belongs to the Ackermann class, i.e. it contains at most one universal first-order quantifier. All properties expressible by ∑₁¹ (Ackermann) sentences are NP-computable, and there are natural NP-complete properties, such as satisfiability, that are expressible by such sentences. It is established that the 0-1 law holds for the class ∑₁¹ (Ackermann), and it is shown that the associated decision problem is NEXPTIME-complete. It is also shown that the 0-1 law fails for other fragments of existential second-order logic in which first-order part belongs to certain prefix classes with an unsolvable decision problem

BibTeX

  @InProceedings{KolaitisVardi-01lawsanddecisionpr,
    author = 	 {Phokion G. Kolaitis and Moshe Y. Vardi},
    title = 	 {0-1 laws and decision problems for fragments of second-order logic },
    booktitle =  {Proceedings of the Third Annual IEEE Symp. on Logic in Computer Science, {LICS} 1988},
    year =	 1988,
    editor =	 {Yuri Gurevich},
    month =	 {July}, 
    pages =      {2--11},
    location =   {Edinburgh, Scotland, UK}, 
    publisher =	 {IEEE Computer Society Press}
  }