Lics

ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Third Annual IEEE Symposium on

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 ∑11 (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 ∑11 (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 ∑11 (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 Symposium on Logic in Computer Science (LICS 1988)},
    year =	 {1988},
    month =	 {July}, 
    pages =      {2--11},
    location =   {Edinburgh, Scotland, UK}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2022-10-3113:49
Sam Staton