On fixed-point logic with counting

DOI10.2307/2586569zbMATH Open0960.03025OpenAlexW2092961415MaRDI QIDQ4508261FDOQ4508261

Authors: Jörg Flum, Martin Grohe 

Publication date: 14 January 2001

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

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

Recommendations

• scientific article; zbMATH DE number 515737
• On polynomial time computation over unordered structures
• The Power of Counting Logics on Restricted Classes of Finite Structures
• The two-variable fragment with counting and equivalence
• Fixed-point logics and computation
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• Logics with counting and equivalence
• Complexity of the two-variable fragment with counting quantifiers
• Logical hierarchies in PTIME
• Tree canonization and transitive closure

zbMATH Keywords

finite model theoryfixed-pointpolynomial timedescriptive complexitycounting logicinflationary fixed-point logic

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Cites Work

• Fixed-point extensions of first-order logic
• An optimal lower bound on the number of variables for graph identification
• Relational queries computable in polynomial time
• Generalized Quantifiers and Logical Reducibilities
• Infinitary logic and inductive definability over finite structures
• The expressive power of fixed-point logic with counting

Cited In (18)

• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• First order logic, fixed point logic and linear order
• Rank logic is dead, long live rank logic!
• Title not available (Why is that?)
• Fixed-point logics and computation
• On polynomial time computation over unordered structures
• Enhancing fixed point logic with cardinality quantifiers
• Maximum matching and linear programming in fixed-point logic with counting
• Tree canonization and transitive closure
• A logical characterization of the counting hierarchy
• The Power of Counting Logics on Restricted Classes of Finite Structures
• On the Descriptive Complexity of Linear Algebra
• Gaifman normal forms for counting extensions of first-order logic
• An analysis of fixed-point queries on binary trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Arrow logic and infinite counting
• Title not available (Why is that?)

This page was built for publication: On fixed-point logic with counting

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