Infinitary logics and 0-1 laws

DOI10.1016/0890-5401(92)90021-7zbMath0762.03016OpenAlexW2063406522MaRDI QIDQ1193591

Phokion G. Kolaitis, Moshe Y. Vardi

Publication date: 27 September 1992

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

Full work available at URL: https://doi.org/10.1016/0890-5401(92)90021-7

zbMATH Keywords

expressive powerfixpoint logics

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Other infinitary logic (03C75)

Related Items (51)

Finite Variable Logics in Descriptive Complexity Theory ⋮ Convergence and Nonconvergence Laws for Random Expansions of Product Structures ⋮ Logical properties of random graphs from small addable classes ⋮ Semantic Restrictions over Second-Order Logic ⋮ Canonization for two variables and puzzles on the square ⋮ How to define a linear order on finite models ⋮ Hierarchies in transitive closure logic, stratified Datalog and infinitary logic ⋮ The Kolmogorov expressive power of Boolean query languages ⋮ 0-1 laws by preservation ⋮ Unification of infinite sets of terms schematized by primal grammars ⋮ SO F : A Semantic Restriction over Second-Order Logic and Its Polynomial-Time Hierarchy ⋮ Preservation theorems in finite model theory ⋮ Pebble games and cospectral graphs ⋮ Expressibility of properties of relations ⋮ The metamathematics of random graphs ⋮ On the Decision Problem for Two-Variable First-Order Logic ⋮ Logical laws for existential monadic second-order sentences with infinite first-order parts ⋮ Unnamed Item ⋮ The expressive power of fixed-point logic with counting ⋮ Strong 0-1 laws in finite model theory ⋮ A topological zero-one law and elementary equivalence of finitely generated groups ⋮ Infinitary logics and very sparse random graphs ⋮ On the expressive power of counting ⋮ Computing with infinitary logic ⋮ A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law ⋮ The \(k\)-variable property is stronger than H-dimension \(k\) ⋮ A semideterministic approach to object creation and nondeterminism in database queries ⋮ Implicit definability and infinitary logic in finite model theory ⋮ A restricted second order logic for finite structures ⋮ On probabilistic elimination of generalized quantifiers ⋮ Degree lower bounds of tower-type for approximating formulas with parity quantifiers ⋮ Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs ⋮ Descriptive complexity of graph spectra ⋮ Whither semantics? ⋮ First order logic, fixed point logic and linear order ⋮ Zero-one law and definability of linear order ⋮ Relating structure and power: comonadic semantics for computational resources (extended abstract) ⋮ Constraint satisfaction, graph isomorphism, and the pebbling comonad ⋮ The strategic balance of games in logic ⋮ Relating Structure and Power: Comonadic Semantics for Computational Resources ⋮ A restricted second order logic for finite structures ⋮ Zero-one laws for \(k\)-variable first-order logic of sparse random graphs ⋮ Almost everywhere elimination of probability quantifiers ⋮ Zero-one laws for sentences with \(k\) variables ⋮ The Relational Polynomial-Time Hierarchy and Second-Order Logic ⋮ Almost Everywhere Equivalence of Logics in Finite Model Theory ⋮ Conjunctive-query containment and constraint satisfaction ⋮ Lower bounds for invariant queries in logics with counting. ⋮ Abstract state machines and computationally complete query languages ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws ⋮ Strong convergence in finite model theory

Cites Work

• Threshold spectra via the Ehrenfeucht game
• 0-1 laws and decision problems for fragments of second-order logic
• Definability with bounded number of bound variables
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On random models of finite power and monadic logic
• Fixed-point extensions of first-order logic
• The computational complexity of asymptotic problems. I: Partial orders
• Upper and lower bounds for first order expressibility
• An observation on time-storage trade off
• Elementary induction on abstract structures
• Hamiltonian circuits in random graphs
• Structure and complexity of relational queries
• Concerning measures in first order calculi
• A lattice-theoretical fixpoint theorem and its applications
• Properties of almost all graphs and complexes
• Complexity of the first-order theory of almost all finite structures
• A zero-one law for logic with a fixed-point operator
• Relational queries computable in polynomial time
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Zero-One Laws for Sparse Random Graphs
• Second-order and Inductive Definability on Finite Structures
• Almost sure theories
• Monadic generalized spectra
• Probabilities on finite models
• On Moschovakis closure ordinals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Infinitary logics and 0-1 laws