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.
Similar content being viewed by others
References
Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: refining Schaefer’s Theorem. J. Comput. Syst. Sci. 75, 245–254 (2009)
Alechina, N., Gurevich, Y.: Syntax vs. semantics on finite structures. In: Mycielski, J., Rozenberg, G., Salomaa, A. (eds.) Structures in Logic and Computer Science. A Selection of Essays in Honor of Ehrenfeucht, A., LNCS, vol. 1261, pp. 14–33. Springer, Berlin (1997)
Barto, L.: The constraint satisfaction problem and universal algebra. Bull. Symb. Logic 21, 319–337 (2015)
Barto, L., Kozik, M.: Absorbing subalgebras, cyclic terms and the constraint satisfaction problem. Log. Methods Comput. Sci. 8(1), 7:1–7:26 (2012)
Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang–Jensen and Hell). SIAM J. Comput. 38, 1782–1802 (2008/2009)
Barto, L., Krokhin, A., Willard, R.: Polymorphisms and how to use them. In: The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-ups, vol. 7, pp. 1–44 (2017)
Bonato, A.: Continuum many universal Horn classes of graphs of bounded chromatic number. Algebra Universalis 40, 105–108 (1998)
Brewster, R.C., Lee, J-B., Moore, B., Noel, J.A., Siggers, M.: On the complexity of two decision problems related to graph homomorphism reconfiguration. Manuscript. arXiv:1712.00200 (2017)
Bulatov, A.A., Jeavons, P.G., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 720–742 (2005)
Burris, S., Sankappanavar, H.P.: A Course in Universal Algebra. Springer, New York (1981)
Caicedo, X.: Finitely axiomatizable quasivarieties of graphs. Algebra Universalis 34, 314–321 (1995)
Chen, H., Larose, B.: Asking the metaquestions in constraint tractability. ACM Trans. Comput. Theory 9, 11:1–11:27 (2017)
Clark, D.M., Davey, B.A., Haviar, M., Pitkethly, J.G., Talukder, M.R.: Standard topological quasi-varieties. Houston J. Math. 4, 859–887 (2003)
Clark, D.M., Davey, B.A., Jackson, M.G., Pitkethly, J.G.: The axiomatizability of topological prevarieties. Adv. Math. 218, 1604–1653 (2008)
Erdős, P.: Graph theory and probability. Can. J. Math. 11, 34–48 (1959)
Erdős, P., Hajnal, A.: On chromatic number of graphs and set-systems. Acta Mathematica Academiae Scientiarum Hungaricae Tomus 17, 61–99 (1966)
Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28, 57–104 (1998)
Gorbunov, V.A.: Algebraic Theory of Quasivarieties. Consultants Bureau, New York (1998)
Ham, L., Jackson, M.: All or nothing: toward a promise problem dichotomy for constraint problems. In: Beck, J.C. (ed.) CP 2017, LNCS, vol. 10416, pp. 139–156 (2017)
Hell, P., Nešetřil, J.: On the complexity of H-coloring. J. Comb. Theory Ser. B 48, 92–110 (1990)
Immerman, N.: Descriptive Complexity. Springer, New York (1999)
Jackson, M.: Flexible constraint satisfiability and a problem in semigroup theory. Manuscript. arXiv:1512.03127 (2015)
Jackson, M., Kowalski, T., Niven, T.: Digraph related constructions and the complexity of digraph homomorphism problems. Int. J. Algebra Comput. 26, 1395–1433 (2016)
Jackson, M., Trotta, B.: Constraint satisfaction, irredundant axiomatisability and continuous colouring. Studia Logica 101, 65–94 (2013)
Jackson, M., McKenzie, R.: Interpreting graph colorability in finite semigroups. Int. J. Algebra Comput. 16, 119–140 (2006)
Jackson, M., Volkov, M.V.: Relatively inherently nonfinitely Q-based finite semigroups. Trans. Am. Math. Soc. 361, 2181–2206 (2009)
Larose, B.: Algebraic methods and the complexity of digraph CSPs: a survey. In: The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-ups, vol. 7, pp. 267–285 (2017)
Libkin, L.: Elements of Finite Model Theory. Texts in Theoretical Computer Science. Springer, Berlin (2004)
Maltsev, A.I.: On the immersion of the associative systems in groups. I. Mat. Sb. 6, 331–336 (1939). (Russian)
Maltsev, A.I.: On the immersion of the associative systems in groups. II. Mat. Sb. 8, 251–264 (1940). (Russian)
Maltsev, A.I.: Algebraic Systems. Springer, Berlin (1973)
Margolis, S.W., Sapir, M.V.: Quasi-identities of finite semigroups and symbolic dynamics. Israel J. Math. 92, 317–331 (1995)
McNulty, G.F.: Fragments of first order logic. I. Universal Horn logic. J. Symb. Logic 42, 221–237 (1977)
Nešetřil, J.: The homomorphism structure of classes of graphs. Comb. Probab. Comput. 8, 177–184 (1999)
Nešetřil, J., Pultr, A.: On classes of relations and graphs determined by subobjects and factorobjects. Discrete Math. 22, 287–300 (1978)
Rosen, E.: Some aspects of model theory and finite structures. Bull. Symb. Logic 8, 380–403 (2002)
Sapir, M.V.: On the quasivarieties generated by finite semigroups. Semigroup Forum 20, 73–88 (1980)
Szekely, Z.: Computational complexity of the finite algebra membership problem for varieties. Int. J. Algebra Comput. 12, 811–823 (2002)
Trotta, B.: Residual properties of simple graphs. Bull. Aust. Math. Soc. 82, 488–504 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by R. Willard.
M. Jackson was supported by ARC Discovery Project DP1094578 and Future Fellowship FT120100666.
Rights and permissions
About this article
Cite this article
Ham, L., Jackson, M. Axiomatisability and hardness for universal Horn classes of hypergraphs. Algebra Univers. 79, 30 (2018). https://doi.org/10.1007/s00012-018-0515-y
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00012-018-0515-y