Computing H-Partitions in ASP and Datalog

Autor:	Capon, Chloé, Lecomte, Nicolas, Wijsen, Jef
Rok vydání:	2022
Předmět:	Computer Science - Databases Computer Science - Artificial Intelligence Computer Science - Logic in Computer Science
Druh dokumentu:	Working Paper
Popis:	A $H$-partition of a finite undirected simple graph $G$ is a labeling of $G$'s vertices such that the constraints expressed by the model graph $H$ are satisfied. For every model graph $H$, it can be decided in non-deterministic polynomial time whether a given input graph $G$ admits a $H$-partition. Moreover, it has been shown by Dantas et al. that for most model graphs, this decision problem is in deterministic polynomial time. In this paper, we show that these polynomial-time algorithms for finding $H$-partitions can be expressed in Datalog with stratified negation. Moreover, using the answer set solver Clingo, we have conducted experiments to compare straightforward guess-and-check programs with Datalog programs. Our experiments indicate that in Clingo, guess-and-check programs run faster than their equivalent Datalog programs. Comment: 17 pages, 8 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2202.03730 Zobrazit plný text záznamu View this record from Arxiv