Probabilities on finite models

From MaRDI portal
Publication:4108321

DOI10.2307/2272945zbMath0341.02044OpenAlexW4235934183MaRDI QIDQ4108321

Ronald Fagin

Publication date: 1976

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

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



Related Items

Convergence and Nonconvergence Laws for Random Expansions of Product Structures, Logical properties of random graphs from small addable classes, The complexity class θp2: Recent results and applications in AI and modal logic, EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs, Logical perspectives on the foundations of probability, Preservation theorems in finite model theory, FINITE RELATION ALGEBRAS, A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth, Logical limit laws for layered permutations and related structures, Preface to the special issue of Permutation Patterns 2021 (PP2021), The almost sure theory of finite metric spaces, Logical laws for short existential monadic second-order sentences about graphs, Unnamed Item, First-order zero-one law for the uniform model of the random graph, SMT-based verification of data-aware processes: a model-theoretic approach, First-Order Model-Checking in Random Graphs and Complex Networks, Degree lower bounds of tower-type for approximating formulas with parity quantifiers, Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview, Infinitary logic for computer science, DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS, THE THEORY OF SPECTRUM EXCHANGEABILITY, Zero-one laws for random graphs with vertices in a Boolean cube, Spectra of short monadic sentences about sparse random graphs, Bounded quantifier depth spectra for random graphs, Listing graphs that satisfy first-order sentences, Asymptotic enumeration and a 0-1 law for $m$-clique free graphs, A note on the Kolmogorov data complexity and nonuniform logical definitions, The finite submodel property and \(\omega\)-categorical expansions of pregeometries, Entropy of formulas, Counting unlabeled structures, Quasi-Random Set Systems, A zero‐one law for a random subset, Nonconvergence, undecidability, and intractability in asymptotic problems, Finitistic proofs of 0-1 laws for fragments of second-order logic, Finite tournaments with a nonempty diamonds' support, A logical approach to asymptotic combinatorics. II: Monadic second-order properties, When does the zero-one \(k\)-law fail?, Probabilities of Sentences about Very Sparse Random Graphs, Probabilities of First-Order Sentences about Unary Functions, A logical approach to asymptotic combinatorics I. First order properties, Limits of schema mappings, On the zero-one \(k\)-law extensions, A Theorem on Reconstruction of Random Graphs, The computational complexity of asymptotic problems. I: Partial orders, How to define a linear order on finite models, Zero-one law for an extension of first-order predicate language, Finitely representable databases, A formal analysis of information disclosure in data exchange, Application of a Tauberian theorem to finite model theory, Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations, Convergence in homogeneous random graphs, On Failure of 0-1 Laws, The Kolmogorov expressive power of Boolean query languages, The First-Order Contiguity of Sparse Random Graphs with Prescribed Degrees, 0-1 laws by preservation, Queries with arithmetical constraints, Extension of the zero-one \(k\)-law, Lower complexity bounds for lifted inference, Quantifier alternation in first-order formulas with infinite spectra, Properties of Classes of Random Graphs, Zero-one \(k\)-law, Graph theoretic models, Subtournaments isomorphic to \(W_5\) in a indecomposable tournament, The metamathematics of random graphs, An efficiently computable subgraph pattern support measure: counting independent observations, Logical laws for existential monadic second-order sentences with infinite first-order parts, Random graph orders, Number of quantifiers is better than number of tape cells, Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false, 0-1 laws and decision problems for fragments of second-order logic, Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination, Infinity and verifiability in Carnap's inductive logic, The emergence of reasons conjecture., A topological zero-one law and elementary equivalence of finitely generated groups, Upper and lower bounds for first order expressibility, A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences, On the effective content of asymptotic verifications of Edgeworth's Conjecture, First order properties of random posets, On the expressive power of counting, A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law, Some thoughts on knowledge-enhanced machine learning, Universal elements and the complexity of certain classes of infinite graphs, Logical limit laws for minor-closed classes of graphs, Distanced graphs, Infinitary logics and 0-1 laws, On the convergence of probabilities of first-order sentences for recursive random graph models, MSO 0-1 law for recursive random trees, Finite-model theory -- A personal perspective, Zero-one laws for random distance graphs with vertices in \(\{0,1\}^n\), Graphs with then-e.c. adjacency property constructed from resolvable designs, Submaps of maps. I: General 0-1 laws, Zero-one law for random distance graphs with vertices in \(\{-1,0,1\}^n\), Existential monadic second order convergence law fails on sparse random graphs, Query evaluation on a database given by a random graph, Descriptive complexity of graph spectra, Determined theories and limit laws, A survey of homogeneous structures, On the two kinds of probability in algebra, The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws, The number of finite relational structures, Probabilities in first—order logic of a unary function and a binary relation, Random graph orders do not satisfy a 0–1 law, Probabilities on Models of Universal Sentences, The many faces of interpolation, Zero-one laws for \(k\)-variable first-order logic of sparse random graphs, Threshold spectra via the Ehrenfeucht game, Zero-One Laws for Sparse Random Graphs, Asymptotic probabilities of extension properties and random \(l\)-colourable structures, On a sequence of random distance graphs subject to the zero-one law, Zero-one laws for random \(k\)-partite graphs, Local properties of query languages, Zero-one laws for sentences with \(k\) variables, Almost Everywhere Equivalence of Logics in Finite Model Theory, Almost all comparability graphs are UPO, Random orders, On random models of finite power and monadic logic, Program schemes, arrays, Lindström quantifiers and zero-one laws, \(\gamma\)-variable first-order logic of uniform attachment random graphs, The 0-1 law fails for monadic existential second-order logic on undirected graphs, Ample simplicial complexes, Simple structures axiomatized by almost sure theories, On the 4-spectrum of first-order properties of random graphs