Journal article

Axiomatisability and hardness for universal Horn classes of hypergraphs

L Ham, M Jackson

Algebra Universalis | Springer | Published : 2018

Abstract

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–Fraïssé 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.

University of Melbourne Researchers

Citation metrics