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

**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 ∑_{1}^{1} (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 ∑_{1}^{1} (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 ∑_{1}^{1} (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} }