Nonconvergence, undecidability, and intractability in asymptotic problems
From MaRDI portal
Publication:1095135
DOI10.1016/0168-0072(87)90017-0zbMath0632.03037MaRDI QIDQ1095135
Kevin J. Compton, Saharon Shelah, C. Ward Henson
Publication date: 1987
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2027.42/26912
permutations; binary functions; binary relations; unary functions; asymptotic probabilities; effective content of asymptotic combinatorics; first-order asymptotic problem; monadic second-order properties
03D35: Undecidability and degrees of sets of sentences
03D15: Complexity of computation (including implicit computational complexity)
05A99: Enumerative combinatorics
Related Items
Counting finite models, Probabilities in first—order logic of a unary function and a binary relation, Zero-one laws with variable probability, On the two kinds of probability in algebra, Finite-model theory -- A personal perspective, A uniform method for proving lower bounds on the computational complexity of logical theories, First order properties of random posets, Metafinite model theory, Zero-one law and definability of linear order, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A uniform method for proving lower bounds on the computational complexity of logical theories
- On random models of finite power and monadic logic
- The computational complexity of logical theories
- A logical approach to asymptotic combinatorics. II: Monadic second-order properties
- Probabilities of First-Order Sentences about Unary Functions
- TWO THEOREMS IN GRAPH THEORY
- An Algorithm for a Minimum Cover of a Graph
- Complexity of the first-order theory of almost all finite structures
- An undecidable problem in finite combinatorics
- A zero-one law for logic with a fixed-point operator
- Application of a Tauberian theorem to finite model theory
- Almost sure theories
- Probabilities on finite models
- Ordered Cycle Lengths in a Random Permutation
- Enumeration of Linear Graphs for Mappings of Finite Sets
- Impossibility of an algorithm for the decision problem in finite classes
- The Expected Number of Components Under a Random Mapping Function