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

DOI10.1007/978-3-642-28279-9_10zbMath1312.68094OpenAlexW168249864MaRDI QIDQ3224003

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

finite model theorydescriptive complexityrelational machines

Mathematics Subject Classification ID

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

Related Items

Semantic Restrictions over Second-Order Logic

Cites Work

• Elements of finite model theory.
• Datalog extensions for database queries and updates
• Infinitary logics and 0-1 laws
• The polynomial-time hierarchy
• A restricted second order logic for finite structures
• A study of homogeneity in relational databases
• Relational queries computable in polynomial time
• On finite rigid structures
• The Relational Polynomial-Time Hierarchy and Second-Order Logic
• Unnamed Item
• Unnamed Item
• Unnamed Item