A logical approach to asymptotic combinatorics. II: Monadic second-order properties

DOI10.1016/0097-3165(89)90009-5zbMath0717.60016OpenAlexW2039607932MaRDI QIDQ2638642

Kevin J. Compton

Publication date: 1989

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(89)90009-5

zbMATH Keywords

monadic second-order logicasymptotic probabilities for all monadic second-order sentencesmonadic second-order 0-1 lawsproblem of determining probabilities of first-order properties

Mathematics Subject Classification ID

Combinatorial probability (60C05) Asymptotic enumeration (05A16) Model theory of finite structures (03C13)

Related Items

ABSTRACT NUMBER SYSTEMS AND LOGICAL LIMIT LAWS, Nonconvergence, undecidability, and intractability in asymptotic problems, Probabilities of Sentences about Very Sparse Random Graphs, Some methods for computing component distribution probabilities in relational structures, Monadic second-order properties of very sparse random graphs, Application of a Tauberian theorem to finite model theory, Asymptotic density in quasi-logarithmic additive number systems, FINITE RELATION ALGEBRAS, Logical laws for short existential monadic second-order sentences about graphs, Strong 0-1 laws in finite model theory, Automatic average-case analysis of algorithms, Counting finite models, Logical limit laws for minor-closed classes of graphs, First-order and monadic properties of highly sparse random graphs, Sufficient conditions for zero-one laws, Enumeration of viral capsid assembly pathways: tree orbits under permutation group action, Asymptotics for logical limit laws: When the growth of the components is in an RT class, Analytic analysis of algorithms, Separating Graph Logic from MSO, DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS

Cites Work

• Unnamed Item
• A logical approach to asymptotic combinatorics I. First order properties
• Probabilities of First-Order Sentences about Unary Functions
• A Generalisation of Stirling's Formula.
• An application of games to the completeness problem for formalized theories
• An undecidable problem in finite combinatorics
• Almost sure theories
• Asymptotic Methods in Enumeration
• Probabilities on finite models
• ON THE CONVERGENCE OF EIGENFUNCTION EXPANSIONS