Digitale Bibliotheek
Sluiten Bladeren door artikelen uit een tijdschrift
<< vorige    volgende >>
     Tijdschrift beschrijving
       Alle jaargangen van het bijbehorende tijdschrift
         Alle afleveringen van het bijbehorende jaargang
           Alle artikelen van de bijbehorende aflevering
                                       Details van artikel 5 van 6 gevonden artikelen
  Properties of Almost All Graphs and Generalized Quantifiers
Titel: Properties of Almost All Graphs and Generalized Quantifiers
Auteur: Dawar, Anuj
Grädel, Erich
Verschenen in: Fundamenta informaticae
Paginering: Jaargang 98 (2010) nr. 4 pagina's 351-372
Jaar: 2010-03-15
Inhoud: 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.
Uitgever: IOS Press
Bronbestand: Elektronische Wetenschappelijke Tijdschriften

                             Details van artikel 5 van 6 gevonden artikelen
<< vorige    volgende >>
 Koninklijke Bibliotheek - Nationale Bibliotheek van Nederland