ASNP: a tame fragment of existential second-order logic

DOI10.1007/978-3-030-51466-2_13OpenAlexW3038004136MaRDI QIDQ2106601

Simon Knäuer, Florian Starke, Manuel Bodirsky

Publication date: 16 December 2022

Full work available at URL: https://arxiv.org/abs/2001.08190

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Universal Horn Sentences and the Joint Embedding Property ⋮ On guarded extensions of MMSNP ⋮ Using model theory to find decidable and tractable description logics with concrete domains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Universal graphs with forbidden subgraphs and algebraic closure
• Datalog and constraint satisfaction with infinite templates
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• Constraints, MMSNP and expander relational structures
• Universal Structures and the Logic of Forbidden Patterns
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Homomorphism and embedding universal structures for restricted classes
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures
• PROJECTIVE CLONE HOMOMORPHISMS
• Ontology-Based Data Access
• A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
• Temporal Constraint Satisfaction Problems in Fixed-Point Logic

This page was built for publication: ASNP: a tame fragment of existential second-order logic