View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Logical Laws on caterpillars

        Thumbnail
        View/Open
        master-thesis.pdf (524.2Kb)
        Publication date
        2016
        Author
        Lambers, R.
        Metadata
        Show full item record
        Summary
        Glebskii et al. (1969) and Fagin (1975) first proved a Zero-One Law with respect to First Order-logic on the Erdos-Renyi random graph \(G(n,p)\) with \(p=\frac12\). Since then, multiple classes of graphs have been proven to obey a Zero-One Law or not, on different kinds of logical languages. The class of labeled caterpillars does not obey a Zero-One law in First Order Logic; however, there's a convergence law, as is proven in this thesis. Subsequently, it's also proven for the class of unlabeled caterpillars. While proving these convergence laws, we use the fact that only the 'outer parts' of a caterpillar can be different, while the 'inside' tends to be the same for large enough caterpillars. In the final chapter we therefore introduce the group of caterpillars, having their outer vertices attached to each other to create bracelets. The class of bracelets is proven to obey a Zero-One Law.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/25107
        Collections
        • Theses
        Utrecht university logo