Probabilities on models of universal sentences
HTML articles powered by AMS MathViewer
- by Douglas N. Hoover PDF
- Proc. Amer. Math. Soc. 98 (1986), 294-297 Request permission
Abstract:
We show that the asymptotics of conditional probabilities of first order universal sentences on finite models are the same as those of general first order sentences. This answers a question of R. Fagin.References
- Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of computation (Proc. SIAM-AMS Sympos., New York, 1973) SIAM-AMS Proc., Vol. VII, Amer. Math. Soc., Providence, R.I., 1974, pp. 43–73. MR 0371622
- Ronald Fagin, Probabilities on finite models, J. Symbolic Logic 41 (1976), no. 1, 50–58. MR 476480, DOI 10.2307/2272945 Y. V. Glebskii, D. I. Kogan, M. I. Liogon’kii, and V. A. Talanov, Range and degree of realizability of formulas in the restricted predicate calculus, Kybernetika (Prague) 5 (1969), 142-154. N. D. Jones and A. L. Selman, Turing machines and the spectra of first order formulas with equality, Proc. 4th ACM Sympos. on Theory of Computing, 1972, pp. 157-167.
Additional Information
- © Copyright 1986 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 98 (1986), 294-297
- MSC: Primary 03C13; Secondary 68Q15
- DOI: https://doi.org/10.1090/S0002-9939-1986-0854036-X
- MathSciNet review: 854036