A zero-one law for logic with a fixed-point operator. (English) Zbl 0608.68077
The logic obtained by adding the least-fixed-point operator to first- order logic was proposed as a query language by A. Aho and J. Ullman [Proc. 6th ACM Symp. Princ. Program. Lang., 110-120 (1979)] and has been studied, particularly in connection with finite models, by numerous authors. We extend to this logic, and to the logic containing the more powerful iterative-fixed-point operator, the zero-one law proved for first-order logic by Yu. V. Glebskij, D. I. Kogan, M. I. Liogon’kij and V. A. Talanov [Kibernetika 1969, No.2, 17-27 (1969; Zbl 0209.308)] and R. Fagin [J. Symb. Logic 41, 50-58 (1976; Zbl 0341.02044)]. For any sentence \(\phi\) of the extended logic, the proportion of models of \(\phi\) among all structures with universe \(\{\) 1,2,...,n\(\}\) approaches 0 or 1 as n tends to infinity. We also show that the problem of deciding, for any \(\phi\), whether this proportion approaches 1 is complete for exponential time, if we consider only \(\phi\) ’s with a fixed finite vocabulary (or vocabularies of bounded arity) and complete for double-exponential time if \(\phi\) is unrestricted. In addition, we establish some related results.
MSC:
68P20 | Information storage and retrieval of data |
60F20 | Zero-one laws |
03C13 | Model theory of finite structures |
03B48 | Probability and inductive logic |
60B10 | Convergence of probability measures |
03C68 | Other classical first-order model theory |
03D15 | Complexity of computation (including implicit computational complexity) |
68Q25 | Analysis of algorithms and problem complexity |