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

DOI10.1016/S0019-9958(85)80027-9zbMATH Open0608.68077MaRDI QIDQ3747760FDOQ3747760

Authors: Andreas Blass, Dexter Kozen, Yuri Gurevich 

Publication date: 1985

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

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

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)

Cited In (25)

• A new zero-one law and strong extension axioms
• Infinitary logics and 0-1 laws
• The Kolmogorov expressive power of Boolean query languages
• Listing graphs that satisfy first-order sentences
• Finite-model theory -- A personal perspective
• 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
• An Asymptotic Analysis of Probabilistic Logic Programming, with Implications for Expressing Projective Families of Distributions
• Zero-one laws for modal logic
• 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
• Title not available (Why is that?)
• Eventual periodicity and ``one-dimensional queries
• Finite Variable Logics in Descriptive Complexity Theory
• Title not available (Why is that?)
• On the expressive power of counting
• Counting finite models

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)