The descriptive complexity of decision problems through logics with relational fixed-point and capturing results

DOI10.1016/j.entcs.2017.04.008zbMath1401.68105OpenAlexW2666358762WikidataQ113317595 ScholiaQ113317595MaRDI QIDQ1744448

Ana Teresa Martins, Márcia Farias, Francicleber Ferreira

Publication date: 23 April 2018

Full work available at URL: https://doi.org/10.1016/j.entcs.2017.04.008

zbMATH Keywords

expressivenessdescriptive complexityfixed-point logicrelational fixed-point logic

Mathematics Subject Classification ID

Logic in computer science (03B70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite model theory and its applications.
• Fixed-point extensions of first-order logic
• Datalog extensions for database queries and updates
• Model theory.
• The polynomial-time hierarchy
• Weak Second‐Order Arithmetic and Finite Automata
• Fixpoint logics, relational machines, and computational complexity
• A relational model of data for large shared data banks

This page was built for publication: The descriptive complexity of decision problems through logics with relational fixed-point and capturing results