0-1 laws and decision problems for fragments of second-order logic

Fragments of existential second-order logic are investigated in which the patterns of first order quantifiers are restricted. The focus is on the class Sigma /sub 1//sup 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 Sigma /sub 1//sup 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 Sigma /sub 1//sup 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.<>