Infinitary logics and 0-1 laws
From MaRDI portal
Publication:1193591
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
Related Items
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?, Zero-one law and definability of linear order, Relating structure and power: comonadic semantics for computational resources (extended abstract), 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
- 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
- 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
