JavaScript is disabled for your browser. Some features of this site may not work without it.
A zero-one law for logic with a fixed-point operator
Blass, Andreas; Gurevich, Yuri; Kozen, Dexter
Blass, Andreas; Gurevich, Yuri; Kozen, Dexter
1985
Citation:Blass, Andreas, Gurevich, Yuri, Kozen, Dexter (1985)."A zero-one law for logic with a fixed-point operator." Information and Control 67(1-3): 70-90. <http://hdl.handle.net/2027.42/25540>
Abstract: The logic obtained by adding the least-fixed-point operator to first-order logic was proposed as a query language by Aho and Ullman (in "Proc. 6th ACM Sympos. on Principles of Programming Languages," 1979, pp. 110-120) 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 in (Glebskii, Kogan, Liogonki, and Talanov (1969), Kibernetika 2, 31-42; Fagin (1976), J. Symbolic Logic 41, 50-58). For any sentence [phi] of the extend 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.