Infinitary logics and 0-1 laws

DOI10.1016/0890-5401(92)90021-7zbMATH Open0762.03016OpenAlexW2063406522MaRDI QIDQ1193591FDOQ1193591

Authors: 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

Recommendations

• Expressive power of infinitary \([0,1]\)-logics
• scientific article; zbMATH DE number 3878917
• Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic
• On infinitary Gödel logics
• scientific article; zbMATH DE number 1163986
• Publication:4893133
• scientific article; zbMATH DE number 29724
• Infinitary logic and inductive definability over finite structures
• Logics of infinite depth
• Infinitary logics and abstract elementary classes

zbMATH Keywords

expressive powerfixpoint logics

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (68)

• Strong convergence in finite model theory
• First order logic, fixed point logic and linear order
• Logical properties of random graphs from small addable classes
• Degree lower bounds of tower-type for approximating formulas with parity quantifiers
• Constraint satisfaction, graph isomorphism, and the pebbling comonad
• The strategic balance of games in logic
• SO(∀∃*) Sentences and Their Asymptotic Probabilities
• Convergence and Nonconvergence Laws for Random Expansions of Product Structures
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Witness quantifiers and 0-1 laws
• Lower bounds for invariant queries in logics with counting.
• Zero-one law and definability of linear order
• 0-1 laws by preservation
• Implicit definability and infinitary logic in finite model theory (extended abstract)
• On the Decision Problem for Two-Variable First-Order Logic
• Zero-one laws for sentences with \(k\) variables
• The Kolmogorov expressive power of Boolean query languages
• A restricted second order logic for finite structures
• Canonization for two variables and puzzles on the square
• Nice infinitary logics
• Abstract state machines and computationally complete query languages
• Expressive power of infinitary \([0,1]\)-logics
• Infinitary logic for computer science
• A zero-one law for logic with a fixed-point operator
• Almost everywhere elimination of probability quantifiers
• Title not available (Why is that?)
• Stability, the finite cover property and 0-1 laws
• Infinitary logics and very sparse random graphs
• Title not available (Why is that?)
• Conjunctive-query containment and constraint satisfaction
• Descriptive complexity of modularity problems on graphs
• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• Strong 0-1 laws in finite model theory
• A restricted second order logic for finite structures
• The expressive power of fixed-point logic with counting
• A topological zero-one law and elementary equivalence of finitely generated groups
• The metamathematics of random graphs
• A local normal form theorem for infinitary logic with unary quantifiers
• Relating structure and power: comonadic semantics for computational resources (extended abstract)
• On probabilistic elimination of generalized quantifiers
• \(\mathrm{SO}^F\): a semantic restriction over second-order logic and its polynomial-time hierarchy
• Zero-one laws for modal logic
• Title not available (Why is that?)
• Unification of infinite sets of terms schematized by primal grammars
• Relating structure and power: comonadic semantics for computational resources
• Whither semantics?
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• Preservation theorems in finite model theory
• How to define a linear order on finite models
• Semantic restrictions over second-order logic
• On asymptotic probabilities in logics that capture \(\mathrm{DSPACE}(\log n)\) in presence of ordering
• Pebble games and cospectral graphs
• Title not available (Why is that?)
• Finite Variable Logics in Descriptive Complexity Theory
• Title not available (Why is that?)
• Expressibility of properties of relations
• Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
• Arrow logic and infinite counting
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• Title not available (Why is that?)
• The Relational Polynomial-Time Hierarchy and Second-Order Logic
• Computing with infinitary logic
• On the expressive power of counting
• A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law
• A semideterministic approach to object creation and nondeterminism in database queries
• The \(k\)-variable property is stronger than H-dimension \(k\)
• Proof of the law of infinite conjunction using the perfect disjunctive normal form

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

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