Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic

DOI10.1002/MALQ.19970430203MaRDI QIDQ4336698zbMATH OpenOpenAlexFDO

Authors Iain Stewart

Publication date 5 November 1997

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19970430203

zbMATH Keywords

zero-one lawsgeneralized quantifiersdescriptive complexity theorypebble gamesEhrenfeucht-Fraissé gamesbounded-variable infinitary logic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other infinitary logic (03C75) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• The Kolmogorov expression complexity of logics
• A zero-one law for logic with a fixed-point operator
• Infinitary logics and 0-1 laws
• 0-1 laws and decision problems for fragments of second-order logic

Cited in

(10)

• Infinitary logics and 0-1 laws
• scientific article; zbMATH DE number 1841815 (Why is no real title available?)
• Zero-one laws for first-order formulas with a bounded quantifier depth
• Generalized hex and logical characterizations of polynomial space
• A zero-one law for logic with a fixed-point operator
• Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview
• Zero-one laws for modal logic
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• Finite-Variable Logics Do Not Have Weak Beth Definability Property
• Finitistic proofs of 0-1 laws for fragments of second-order logic

This page was built for publication: Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic

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