Expressive Power of Homomorhpism Query Algorithms
Arnar Ágúst Kristjánsson

Abstract:
A query algorithm based on homomorphism counts is a procedure for deciding membership in a class of finite relational structures using only homomorphism count queries. A left query algorithm can ask for the number of homomorphisms from any structure to the input structure, while a right query algorithm can ask for the number of homomorphisms from the input structure to any other structure.
We systematically compare the expressive power of various types of left and right query algorithms, including non-adaptive query algorithms, adaptive query algorithms that can ask a bounded number of queries, and adaptive query algorithms that can ask an unbounded number of queries. Among other results, we show that there exist classes that cannot be decided by adaptive left query algorithms with a bounded number of queries. We also provide a complete comparison of the expressive power of adaptive and non-adaptive left query algorithms.
We further consider query algorithms in which the homomorphism counting is done over the Boolean semiring B, so that only the existence of a homomorphism is recorded, not the precise number of them. We characterize the expressive power of adaptive unbounded query algorithms over B and use this characterization to derive simpler descriptions in the special cases of homomorphic equivalence classes, CSPs, and Datalog-definable classes.
Finally, we investigate the question of whether counting over ℕ, rather than B, increases the expressive power of these query algorithms. We answer this question affirmatively for all adaptive query algorithms considered.