A logical approach to asymptotic combinatorics. II: Monadic second-order properties
From MaRDI portal
Publication:2638642
DOI10.1016/0097-3165(89)90009-5zbMath0717.60016MaRDI QIDQ2638642
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
monadic second-order logic; asymptotic probabilities for all monadic second-order sentences; monadic second-order 0-1 laws; problem of determining probabilities of first-order properties
60C05: Combinatorial probability
05A16: Asymptotic enumeration
03C13: Model theory of finite structures
Related Items
Counting finite models, Asymptotics for logical limit laws: When the growth of the components is in an RT class, ABSTRACT NUMBER SYSTEMS AND LOGICAL LIMIT LAWS, Logical laws for short existential monadic second-order sentences about graphs, Analytic analysis of algorithms, DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS, First-order and monadic properties of highly sparse random graphs, Enumeration of viral capsid assembly pathways: tree orbits under permutation group action, Nonconvergence, undecidability, and intractability in asymptotic problems, Some methods for computing component distribution probabilities in relational structures, Automatic average-case analysis of algorithms, Logical limit laws for minor-closed classes of graphs, Monadic second-order properties of very sparse random graphs, Strong 0-1 laws in finite model theory, Sufficient conditions for zero-one laws, Asymptotic density in quasi-logarithmic additive number systems, Separating Graph Logic from MSO, Application of a Tauberian theorem to finite model theory, Probabilities of Sentences about Very Sparse Random Graphs
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