Axiomatisability and hardness for universal Horn classes of hypergraphs

作者：Ham Lucy^*; Jackson Marcel

来源：ALGEBRA UNIVERSALIS, 2018, 79(2): UNSP 30.

DOI：10.1007/s00012-018-0515-y

• Universal Horn class
• Hypergraph
• Constraint satisfaction
• SP-preservation

We consider hypergraphs as symmetric relational structures. In this setting, we characterise finite axiomatisability for finitely generated universal Horn classes of loop-free hypergraphs. An Ehrenfeucht-Fraiss'e game argument is employed to show that the results continue to hold when restricted to first order definability amongst finite structures. We are also able to show that every interval in the homomorphism order on hypergraphs contains a continuum of universal Horn classes and conclude the article by characterising the intractability of deciding membership in universal Horn classes generated by finite loop-free hypergraphs.

• 出版日期2018-6