A zero-one law for logic with a fixed-point operator

DOI10.1016/S0019-9958(85)80027-9MaRDI QIDQ3747760zbMATH OpenFDO

Authors Andreas Blass, Dexter Kozen, Yuri Gurevich

Publication date 1985

Published in Information and Control (Search for Journal in Brave)

zbMATH Keywords

finite graphsfirst-order logicinductive logicfinite relational structuresleast- fixed-point operator

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Probability and inductive logic (03B48) Model theory of finite structures (03C13) Zero-one laws (60F20) Complexity of computation (including implicit computational complexity) (03D15) Other classical first-order model theory (03C68)

Recommendations

• Zero-one law for an extension of first-order predicate language
• Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic
• Publication:3204446
• Infinitary logics and 0-1 laws
• The expressive power of fixed-point logic with counting

Cited in

(25)

• Counting finite models
• A new zero-one law and strong extension axioms
• Infinitary logics and 0-1 laws
• The Kolmogorov expressive power of Boolean query languages
• Finite-model theory -- A personal perspective
• Listing graphs that satisfy first-order sentences
• The computational complexity of asymptotic problems. I: Partial orders
• Algorithmic correspondence and completeness in modal logic. V. Recursive extensions of SQEMA
• Fixed-point extensions of first-order logic
• Infinitary logic for computer science
• Asymptotic probabilities of existential second-order Gödel sentences
• Nonconvergence, undecidability, and intractability in asymptotic problems
• 0-1 laws and decision problems for fragments of second-order logic
• Zero-one law for an extension of first-order predicate language
• Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
• Zero-one laws for modal logic
• An Asymptotic Analysis of Probabilistic Logic Programming, with Implications for Expressing Projective Families of Distributions
• Convergence and Nonconvergence Laws for Random Expansions of Product Structures
• When is arithmetic possible?
• On asymptotic probabilities in logics that capture \(\mathrm{DSPACE}(\log n)\) in presence of ordering
• scientific article; zbMATH DE number 4181311 (Why is no real title available?)
• Eventual periodicity and ``one-dimensional queries
• Finite Variable Logics in Descriptive Complexity Theory
• scientific article; zbMATH DE number 7438576 (Why is no real title available?)
• On the expressive power of counting

This page was built for publication: A zero-one law for logic with a fixed-point operator

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