Axiomatisability and hardness for universal Horn classes of hypergraphs

DOI10.1007/s00012-018-0515-yOpenAlexW2964242792WikidataQ129956885 ScholiaQ129956885MaRDI QIDQ1652862

Lucy Ham, Marcel Jackson

Publication date: 16 July 2018

Published in: Algebra Universalis (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphconstraint satisfactionuniversal Horn classSP-preservation

Mathematics Subject Classification ID

Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quasivarieties (08C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures, On varieties of flat nil-semirings, Some nil-ai-semiring varieties, From \(A\) to \(B\) to \(Z\), Nonfinitely based ai-semirings with finitely based semigroup reducts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constraint satisfaction, irredundant axiomatisability and continuous colouring
• Elements of finite model theory.
• The axiomatizability of topological prevarieties
• The complexity of satisfiability problems: Refining Schaefer's theorem
• On the complexity of H-coloring
• On the quasivarieties generated by finite semigroups
• On classes of relations and graphs determined by subobjects and factorobjects
• Finitely axiomatizable quasivarieties of graphs
• Quasi-identities of finite semigroups and symbolic dynamics
• Continuum many universal Horn classes of graphs of bounded chromatic number
• THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• RESIDUAL PROPERTIES OF SIMPLE GRAPHS
• Graph Theory and Probability
• Relatively inherently nonfinitely q-based semigroups
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Fragments of first order logic, I: universal Horn logic
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Homomorphism Structure of Classes of Graphs
• Some Aspects of Model Theory and Finite Structures
• Asking the Metaquestions in Constraint Tractability
• Complexity and polymorphisms for digraph constraint problems under some basic constructions
• Classifying the Complexity of Constraints Using Finite Algebras
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• On chromatic number of graphs and set-systems