The Relational Polynomial-Time Hierarchy and Second-Order Logic

DOI10.1007/978-3-540-88594-8_3zbMath1166.68013OpenAlexW1842425231MaRDI QIDQ5504578

Flavio Ferrarotti, Jose Maria Turull Torres

Publication date: 22 January 2009

Published in: Semantics in Data and Knowledge Bases (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-88594-8_3

zbMATH Keywords

relational complexityrestricted second-order logic

Mathematics Subject Classification ID

Related Items (2)

Semantic Restrictions over Second-Order Logic ⋮ SO F : A Semantic Restriction over Second-Order Logic and Its Polynomial-Time Hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Computing with infinitary logic
• Computable queries for relational data bases
• Datalog extensions for database queries and updates
• Infinitary logics and 0-1 laws
• The polynomial-time hierarchy
• Reflective relational machines
• A restricted second order logic for finite structures
• Computing with first-order logic
• Infinitary logic and inductive definability over finite structures
• A study of homogeneity in relational databases
• Fixpoint logics, relational machines, and computational complexity

This page was built for publication: The Relational Polynomial-Time Hierarchy and Second-Order Logic