{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:25:38Z","timestamp":1777645538179,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>We study 0-1 laws for extensions of first-order logic by Lindstr\u00f6m quantifiers. We state sufficient conditions on a quantifier Q expressing a graph property, for the logic FO[Q] \u2013 the extension of first-order logic by means of the quantifier Q \u2013 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.<\/jats:p>","DOI":"10.3233\/fi-2010-232","type":"journal-article","created":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T23:27:24Z","timestamp":1575329244000},"page":"351-372","source":"Crossref","is-referenced-by-count":3,"title":["Properties of Almost All Graphs and Generalized Quantifiers"],"prefix":"10.1177","volume":"98","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[{"name":"University of Cambridge, Cambridge CB3 0FD, England.\r\t\t\t E-mail: anuj.dawar@cl.cam.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erich","family":"Gr\u00e4del","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, D-52056 Aachen, Germany.\r\t\t\t E-mail: graedel@logic.rwth-aachen.de"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2010,3,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2010-232","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2010-232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:32:29Z","timestamp":1777444349000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2010-232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.3233\/FI-2010-232"],"URL":"https:\/\/doi.org\/10.3233\/fi-2010-232","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3]]}}}