2026-09-17T02:04:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24141 2026-09-05T18:34:13Z ddc:004 open_access

Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts ten Cate, Balder Kolaitis, Phokion G. Kristjánsson, Arnar Á. Query algorithms homomorphisms homomorphism counts directed graphs relational structures Datalog constraint satisfaction A query algorithm based on homomorphism counts is a procedure to decide membership for a class of finite relational structures using only homomorphism count queries. A left query algorithm can ask the number of homomorphisms from any structure to the input structure and a right query algorithm can ask the number of homomorphisms from the input structure to any other structure. We systematically compare the expressive power of different types of left or 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. We also consider query algorithms where the homomorphism counting is done over the Boolean semiring 𝔹, meaning that only the existence of a homomorphism is recorded, not the precise number of them. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Balder ten Cate and Phokion G. Kolaitis and Arnar Á. Kristjánsson 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.34 urn:nbn:de:0030-drops-241413 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.34 eng https://creativecommons.org/licenses/by/4.0/legalcode