On probabilistic elimination of generalized quantifiers

DOI10.1002/RSA.1016MaRDI QIDQ2748424zbMATH OpenOpenAlexFDO

Authors Risto Kaila

Publication date 4 November 2002

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.1016

zbMATH Keywords

almost sure quantifier eliminationconvergence lawsgeneralized quantifierszero-one laws

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Model theory of finite structures (03C13) Other infinitary logic (03C75)

Review text

Let \(Q\) be a collection of generalized quantifiers. The author gives a convenient characterization for the cases where the logic \(L^\omega_{\infty\omega}(Q)\) has almost sure quantifier elimination [in the sense of \textit{Yu. V. Glebskij}, \textit{D. I. Kogan}, \textit{M. I. Liogon'kij} and \textit{V. A. Talanov}, Kibernetika 1969, No. 2, 17-27 (1969; Zbl 0209.30803) and \textit{R. Fagin}, J. Symb. Log. 41, 50-58 (1976; Zbl 0341.02044)]. The results provide a method to prove zero-one and convergence laws for these logics. The paper contains many extensions of known zero-one laws.

Recommendations

• On Almost Sure Elimination of Numerical Quantifiers
• Almost everywhere elimination of probability quantifiers
• Convergence Laws for Very Sparse Random Structures with Generalized Quantifiers
• Witness quantifiers and 0-1 laws
• scientific article; zbMATH DE number 1163931

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• Almost sure theories
• An extension of 0‐1 laws
• Generalized quantifiers and pebble games on finite structures
• Hierarchies of monadic generalized quantifiers
• Infinitary logics and 0-1 laws
• Infinitary logics and very sparse random graphs
• Random sparse unary predicates
• Unary quantifiers on finite models
• Zero-one laws with variable probability

Cited in

(13)

• Bucket elimination: A unifying framework for reasoning
• Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination
• Quantifier Elimination for Quantified Propositional Logics on Kripke Frames of Type
• scientific article; zbMATH DE number 5526522 (Why is no real title available?)
• Almost everywhere elimination of probability quantifiers
• On vectorizations of unary generalized quantifiers
• On Almost Sure Elimination of Numerical Quantifiers
• Convergence Laws for Very Sparse Random Structures with Generalized Quantifiers
• The generality of the zero-one laws
• Random expansions of finite structures with bounded degree
• A general approach to asymptotic elimination of aggregation functions and generalized quantifiers
• First-order logic with equicardinality in random graphs
• A convergence law for continuous logic and continuous structures with finite domains

This page was built for publication: On probabilistic elimination of generalized quantifiers

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