2022/02/08 by Chloé Capon, Nicolas Lecomte, Capon, Chloé +3
Computer Science · #Logic, Reasoning, and Knowledge #Natural Language Processing Techniques #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2202.03730
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.