Paper: 0-1 laws and decision problems for fragments of second-order logic (at LICS 1988)
Authors: Phokion G. Kolaitis Moshe Y. VardiAbstract
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 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} }