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

DOI10.1016/S0019-9958(85)80027-9zbMath0608.68077MaRDI QIDQ3747760

Andreas Blass, Dexter Kozen, Yuri Gurevich

Publication date: 1985

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

zbMATH Keywords

first-order logicinductive logicfinite graphsfinite relational structuresleast- fixed-point operator

Mathematics Subject Classification ID

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

Related Items (20)

Finite Variable Logics in Descriptive Complexity Theory ⋮ Listing graphs that satisfy first-order sentences ⋮ Convergence and Nonconvergence Laws for Random Expansions of Product Structures ⋮ Fixed-point extensions of first-order logic ⋮ Nonconvergence, undecidability, and intractability in asymptotic problems ⋮ Asymptotic probabilities of existential second-order Gödel sentences ⋮ The computational complexity of asymptotic problems. I: Partial orders ⋮ Zero-one law for an extension of first-order predicate language ⋮ The Kolmogorov expressive power of Boolean query languages ⋮ An Asymptotic Analysis of Probabilistic Logic Programming, with Implications for Expressing Projective Families of Distributions ⋮ Algorithmic correspondence and completeness in modal logic. V. Recursive extensions of SQEMA ⋮ Unnamed Item ⋮ 0-1 laws and decision problems for fragments of second-order logic ⋮ When is arithmetic possible? ⋮ On the expressive power of counting ⋮ Counting finite models ⋮ Infinitary logics and 0-1 laws ⋮ Finite-model theory -- A personal perspective ⋮ Infinitary logic for computer science ⋮ Strong extension axioms and Shelah's zero-one law for choiceless polynomial time

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