SO^F: a semantic restriction over second-order logic and its polynomial-time hierarchy

DOI10.1007/978-3-642-28279-9_10MaRDI QIDQ3224003zbMATH OpenOpenAlexFDO

Authors Alejandro L. Grosso, Jose Maria Turull Torres

Publication date 9 March 2012

Published in Conceptual Modelling and Its Theoretical Foundations (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-28279-9_10

zbMATH Keywords

descriptive complexityfinite model theoryrelational machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• The Relational Polynomial-Time Hierarchy and Second-Order Logic
• A restricted second-order logic for non-deterministic poly-logarithmic time
• Semantic restrictions over second-order logic
• Capturing complexity classes by fragments of second-order logic
• Complexity and expressive power of second-order extended Horn logic

Cites work

• A restricted second order logic for finite structures
• A study of homogeneity in relational databases
• Datalog extensions for database queries and updates
• Elements of finite model theory.
• scientific article; zbMATH DE number 17544 (Why is no real title available?)
• scientific article; zbMATH DE number 1302020 (Why is no real title available?)
• Infinitary logics and 0-1 laws
• On finite rigid structures
• Redundant relations in relational databases: a model theoretic perspective
• Relational queries computable in polynomial time
• The polynomial-time hierarchy
• The Relational Polynomial-Time Hierarchy and Second-Order Logic

Cited in

(4)

• Semantic restrictions over second-order logic
• Complexity and expressive power of second-order extended Horn logic
• The Relational Polynomial-Time Hierarchy and Second-Order Logic
• A restricted second order logic for finite structures

This page was built for publication: \(\mathrm{SO}^F\): a semantic restriction over second-order logic and its polynomial-time hierarchy

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