The decision problem for the probabilities of higher-order properties
Phokion G. Kolaitis, Moshe Y. Vardi · 1987
The probability of a property on the class of all finite relational structures is the limit as n → ∞ of the fraction of structures with n elements satisfying the property, provided the limit exists. It is known that 0-1 laws hold for any property expressible in first-order logic or in fixpoint logic, i.e. the probability of any such property exists and is either 0 or 1. It is also known that the associated decision problem for the probabilities is PSPACE-complete and EXPTIME-complete for first-order logic and fixpoint logic respectively. The 0-1 law fails, however, in general for second-order properties and the decision problem becomes unsolvable.