Properties of Almost All Graphs and Generalized Quantifiers

• Autorzy: Dawar A. , Grädel E.
• Języki publikacji: EN

Abstrakty

EN

We study 0-1 laws for extensions of first-order logic by Lindström quantifiers. We state sufficient conditions on a quantifier Q expressing a graph property, for the logic FO[Q] – the extension of first-order logic by means of the quantifier Q – to have a 0-1 law. We use these conditions to show, in particular, that FO[Rig], where Rig is the quantifier expressing rigidity, has a 0-1 law. We also show that extensions of first-order logic with quantifiers for Hamiltonicity, regularity and self-complementarity of graphs do not have a 0-1 law. Blass and Harary pose the question whether there is a logic which is powerful enough to express Hamiltonicity or rigidity and which has a 0-1 law. It is a consequence of our results that there is no such regular logic (in the sense of abstract model theory) in the case of Hamiltonicity, but there is one in the case of rigidity. We also consider sequences of vectorized quantifiers, and show that the extensions of first-order logic obtained by adding such sequences generated by quantifiers that are closed under substructures have 0-1 laws. The positive results also extend to the infinitary logic with finitely many variables.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 98, nr 4
• Strony: 351--372
• Opis fizyczny: Bibliogr. 22 poz.,

Twórcy

autor

Dawar A.

autor

Grädel E.

• University of Cambridge Cambridge CB3 0FD, England,

Bibliografia

• [1] A. Blass, Y. Gurevich, and D. Kozen, A zero-one law for logic with a fixed point operator, Information and Control 67 (1985), 70-90.
• [2] A. Blass, G. Exoo, and F. Harary, Payley Graphs Satisfy All First-Order Adjacency Axioms, Journal of Graph Theory 5 (1981), 435-439.
• [3] A. Blass and F. Harary, Properties of almost all graphs and complexes, Journal of Graph Theory 3 (1979), 225-240.
• [4] B. Bollobás, Random Graphs, Cambridge University Press, 2nd edition, 2001.
• [5] K.J. Compton, 0-1 laws in logic and combinatorics, in: I. Rival (Ed.), NATO Advanced Study Institute on Algorithms and Order, pages 353-383, Kluwer, 1989.
• [6] A. Dawar. Generalized quantifiers and logical reducibilities, Journal of Logic and Computation, 5 (1995), 213-226.
• [7] A. Dawar and E.Grädel. Generalized quantifiers and 0-1 laws. Proc. 10th IEEE Symp. on Logic in Computer Science (1995), 54-64.
• [8] H.-D. Ebbinghaus, Extended logics: The general framework, in: J. Barwise and S. Feferman (Eds.), Model-Theoretic Logics, pages 25-76, Springer-Verlag, New York, 1985.
• [9] H-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 2nd edition, 1999.
• [10] R. Fagin, Probabilities on finite models, Journal of Symbolic Logic 41 (1976), 50-58.
• [11] G. Fayolle, S. Grumbach, and C. Tollu, Asymptotic probabilities of languages with generalized quantifiers, Proc. 8th IEEE Symp. on Logic in Computer Science (1993).
• [12] Y. V. Glebskiı, D. I. Kogan, M.I. Ligon'ki˘ı, and V. A. Talanov, Range and degree of realizability of formulas in the restricted predicate calculus, Kibernetika, 2 (1969), 17-28.
• [13] E. Grandjean, Complexity of the first-order theory of almost all structures, Information and Control, 52 (1983), 180-204.
• [14] M. Grohe, Fixed-point logics on planar graphs. Proc. 13th IEEE Symp. on Logic in Computer Science (1998), 6-15.
• [15] Y. Gurevich, Zero-One Laws, in: The Logic in Computer Science column, EATCS Bulletin 46 (1992), 90-106.
• [16] Risto Kaila. On probabilistic elimination of generalized quantifiers. Random Struct. Algorithms, 19 (2001), 1-36.
• [17] Ph. G. Kolaitis and M. Y. Vardi, 0-1 laws and decision problems for fragments of second-order logic, Information and Computation, 87 (1990), 302-338.
• [18] Ph. G. Kolaitis and M. Y. Vardi, Infinitary logics and 0-1 laws, Information and Computation, 98 (1992), 258-294.
• [19] L. Libkin. Elements of Finite Model Theory. Springer, 2004.
• [20] P. Lindström, First order predicate logic with generalized quantifiers, Theoria, 32 (1966), 186-195.
• [21] V. Talanov, Asymptotic Solvability of Logical Formulae, in: Combinatorial-Algebraic Methods in Applied Mathematics, Gorky University (1981), 118-126 (in Russian). Math. Reviews 85i:03081.
• [22] V. Talanov and V. Knyazev, The Asymptotic Truth Value of Infinite Formulae, Proc. of the All-Union Seminar of Discrete Math. and its Applications, Moscow (1986), 55-61 (in Russian). Math. Reviews 89g:03054.