An undecidable problem in finite combinatorics

DOI10.2307/2274138zbMATH Open0591.03020OpenAlexW2013122733MaRDI QIDQ3718693FDOQ3718693

Authors: Kevin J. Compton 

Publication date: 1984

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2274138

Recommendations

• Nonconvergence, undecidability, and intractability in asymptotic problems
• A logical approach to asymptotic combinatorics I. First order properties
• scientific article; zbMATH DE number 3984616
• Asymptotic conditional probabilities: The non-unary case
• 0-1 laws and decision problems for fragments of second-order logic

zbMATH Keywords

finitely axiomatizable classasymptotic probability of a sentenceundecidable set of sentences

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic Methods in Enumeration
• The number of finite relational structures
• Almost sure theories
• Monotonicity of partition functions
• Title not available (Why is that?)

Cited In (20)

• A codicity undecidable problem in the plane.
• Title not available (Why is that?)
• On random models of finite power and monadic logic
• A logical approach to asymptotic combinatorics I. First order properties
• Title not available (Why is that?)
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• Title not available (Why is that?)
• Nonconvergence, undecidability, and intractability in asymptotic problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of the first-order theory of almost all finite structures
• Title not available (Why is that?)
• On 0, 1-laws and asymptotics of definable sets in geometric Fraïssé classes
• On the effective content of asymptotic verifications of Edgeworth's Conjecture
• Probabilities on Models of Universal Sentences
• Zero-one laws with variable probability
• Application of a Tauberian theorem to finite model theory
• Probabilities of First-Order Sentences about Unary Functions
• The undecidability of joint embedding for 3-dimensional permutation classes

This page was built for publication: An undecidable problem in finite combinatorics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3718693)