ASNP: a tame fragment of existential second-order logic

DOI10.1007/978-3-030-51466-2_13MaRDI QIDQ2106601zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Simon Knäuer, Florian Starke

Publication date 16 December 2022

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
• Partially ordered connectives and monadic monotone strict NP
• On guarded extensions of MMSNP
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• On the complexity of MMSNP

Cites work

• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
• Constraints, MMSNP and expander relational structures
• Datalog and constraint satisfaction with infinite templates
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• Graph structure and monadic second-order logic. A language-theoretic approach
• Homomorphism and embedding universal structures for restricted classes
• On the Structure of Polynomial Time Reducibility
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• PROJECTIVE CLONE HOMOMORPHISMS
• Temporal constraint satisfaction problems in fixed-point logic
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• Universal Structures and the Logic of Forbidden Patterns
• Universal graphs with forbidden subgraphs and algebraic closure

Cited in

(6)

• On guarded extensions of MMSNP
• ASNP: a tame fragment of existential second-order logic
• Existential Fixed-Point Logic as a Fragment of Second-Order Logic
• Using model theory to find decidable and tractable description logics with concrete domains
• Universal Horn Sentences and the Joint Embedding Property
• Forbidden tournaments and the orientation completion problem

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

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