The expressive power of fixed-point logic with counting

DOI10.2307/2275602zbMath0854.03024OpenAlexW2097212968MaRDI QIDQ4879905

Martin Otto

Publication date: 13 January 1997

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275602

zbMATH Keywords

finite model theorydescriptive complexityEhrenfeucht-Fraïssé gamesinfinitary logicsLindström quantifierfixed-point logicscardinalities of definable relationscounting pebble gamesrelational model of computation

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other infinitary logic (03C75)

Related Items (11)

Semantic Restrictions over Second-Order Logic ⋮ Canonization for two variables and puzzles on the square ⋮ How to define a linear order on finite models ⋮ Metafinite model theory ⋮ Capturing the polynomial hierarchy by second-order revised Krom logic ⋮ On the Descriptive Complexity of Linear Algebra ⋮ Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus ⋮ Metafinite model theory ⋮ Large finite structures with few \(L^k\)-types ⋮ Adding for-loops to first-order logic ⋮ On fixed-point logic with counting

Cites Work

• Fixed-point extensions of first-order logic
• Upper and lower bounds for first order expressibility
• Datalog extensions for database queries and updates
• Infinitary logics and 0-1 laws
• An optimal lower bound on the number of variables for graph identification
• Infinitary logic and inductive definability over finite structures
• Relational queries computable in polynomial time

This page was built for publication: The expressive power of fixed-point logic with counting