Almost Everywhere Equivalence of Logics in Finite Model Theory
From MaRDI portal
Publication:3128483
DOI10.2307/421173>zbMath0869.03019>OpenAlexW2033233376>MaRDI QIDQ3128483>
Lauri Hella, Kerkko Luosto, Phokion G. Kolaitis
Publication date: 2 September 1997
Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/cae2ae8a995f764c32968b7ceaf934aaca50b551
Related Items (14)
Finite Variable Logics in Descriptive Complexity Theory ⋮ A note on the Kolmogorov data complexity and nonuniform logical definitions ⋮ How to define a linear order on finite models ⋮ The metamathematics of random graphs ⋮ Strong 0-1 laws in finite model theory ⋮ On probabilistic elimination of generalized quantifiers ⋮ Degree lower bounds of tower-type for approximating formulas with parity quantifiers ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Zero-one law and definability of linear order ⋮ Fixed-Point Definability and Polynomial Time ⋮ Almost everywhere elimination of probability quantifiers ⋮ Adding for-loops to first-order logic ⋮ Stability theory, permutations of indiscernibles, and embedded finite models ⋮ Strong convergence in finite model theory
Cites Work
- Definability with bounded number of bound variables
- On random models of finite power and monadic logic
- Fixed-point extensions of first-order logic
- Infinitary logics and 0-1 laws
- An optimal lower bound on the number of variables for graph identification
- Structure and complexity of relational queries
- Generalized quantifiers and pebble games on finite structures
- Relational queries computable in polynomial time
- Languages that Capture Complexity Classes
- Random Graph Isomorphism
- Monadic generalized spectra
- Probabilities on finite models
- Unnamed Item
- Unnamed Item
This page was built for publication: Almost Everywhere Equivalence of Logics in Finite Model Theory
