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

DOI10.1002/MALQ.19970430203zbMATH Open0876.03020OpenAlexW2065195009MaRDI QIDQ4336698FDOQ4336698

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• Infinitary logics and 0-1 laws
• Title not available (Why is that?)
• 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)