Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911256543232000 |
|---|---|
| author | Cate, Balder ten Kolaitis, Phokion G. Kristjánsson, Arnar Á. |
| author_facet | Cate, Balder ten Kolaitis, Phokion G. Kristjánsson, Arnar Á. |
| contents | 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 $\mathbb{B}$, meaning that only the existence of a homomorphism is recorded, not the precise number of them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16567 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts Cate, Balder ten Kolaitis, Phokion G. Kristjánsson, Arnar Á. Logic in Computer Science 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 $\mathbb{B}$, meaning that only the existence of a homomorphism is recorded, not the precise number of them. |
| title | Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2504.16567 |