Semantic restrictions over second-order logic

DOI10.1007/978-3-642-36008-4_8MaRDI QIDQ3458159zbMATH OpenOpenAlexFDO

Authors Flavio Ferrarotti, Alejandro L. Grosso, Jose Maria Turull Torres

Publication date 8 December 2015

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-642-36008-4_8

Mathematics Subject Classification ID

Higher-order logic (03B16) Logic in computer science (03B70) Database theory (68P15) Descriptive complexity and finite models (68Q19) Semantics in the theory of computing (68Q55)

Recommendations

• \(\mathrm{SO}^F\): a semantic restriction over second-order logic and its polynomial-time hierarchy
• A restricted second order logic for finite structures
• On fragments of higher order logics that on finite structures collapse to second order
• Capturing complexity classes by fragments of second-order logic
• scientific article; zbMATH DE number 176527

Cites work

• \(\mathrm{SO}^F\): a semantic restriction over second-order logic and its polynomial-time hierarchy
• A restricted second order logic for finite structures
• An optimal lower bound on the number of variables for graph identification
• Datalog extensions for database queries and updates
• Finite Variable Logics in Descriptive Complexity Theory
• Fixed-point extensions of first-order logic
• Fixpoint logics, relational machines, and computational complexity
• Generalized quantifiers and pebble games on finite structures
• scientific article; zbMATH DE number 979011 (Why is no real title available?)
• scientific article; zbMATH DE number 5060895 (Why is no real title available?)
• Infinitary logics and 0-1 laws
• On Moschovakis closure ordinals
• On the complexity of entailment in propositional multivalued logics
• Redundant relations in relational databases: a model theoretic perspective
• Relational queries computable in polynomial time
• Subclasses of binary NP
• The expressive power of fixed-point logic with counting
• The polynomial-time hierarchy
• The Relational Polynomial-Time Hierarchy and Second-Order Logic

Cited in

(2)

• \(\mathrm{SO}^F\): a semantic restriction over second-order logic and its polynomial-time hierarchy
• A restricted second order logic for finite structures

This page was built for publication: Semantic restrictions over second-order logic

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