Coloring rules for finite trees, and probabilities of monadic second order sentences
From MaRDI portal
Publication:4345363
DOI<453::AID-RSA3>3.0.CO;2-T 10.1002/(SICI)1098-2418(199707)10:4<453::AID-RSA3>3.0.CO;2-TzbMath0872.03021OpenAlexW2081349727MaRDI QIDQ4345363
Publication date: 6 October 1997
Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199707)10:4<453::aid-rsa3>3.0.co;2-t
Boolean functionEhrenfeucht-Fraïssé gameslimiting probabilitiesfinite rooted treeasymptotic behavior of the fraction of \(n\) vertex trees with a given root colorcoloring rulesmonadic second-order sentence
Trees (05C05) Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Boolean functions (06E30) Model theory of finite structures (03C13) Directed graphs (digraphs), tournaments (05C20)
Related Items
The fraction of large random trees representing a given Boolean function in implicational logic, A sprouting tree model for random boolean functions, On the number of matchings of a tree, Non-redundant random generation algorithms for weighted context-free grammars, Fuzzy logics – quantitatively, Formulae and Asymptotics for Coefficients of Algebraic Functions, Enumerating lambda terms by weighted length of their de Bruijn representation, On the structure of random unlabelled acyclic graphs., Logical limit laws for minor-closed classes of graphs, MSO 0-1 law for recursive random trees, Enumeration of viral capsid assembly pathways: tree orbits under permutation group action, Complexity and Limiting Ratio of Boolean Functions over Implication, Generalised and quotient models for random and/or~trees and application to satisfiability, Recursion and growth estimates in renormalizable quantum field theory, Statistical properties of lambda terms, Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results
