Distributed Answer Set Coloring: Stable Models Computation via Graph Coloring
Answer Set Programming (ASP) is a famous logic language for knowledge representation, which has been really successful in the last years, as witnessed by the great interest into the development of efficient solvers for ASP. Yet, the great request of resources for certain types of problems, as the planning ones, still constitutes a big limitation for problem solving. Particularly, in the case the program is grounded before the resolving phase, an exponential blow up of the grounding can generate a huge ground file, infeasible for single machines with limited resources, thus preventing even the discovering of a single non-optimal solution. To address this problem, in this paper we present a distributed approach to ASP solving, exploiting distributed computation benefits in order to overcome the just explained limitations. The here presented tool, which is called Distributed Answer Set Coloring (DASC), is a pure solver based on the well-known Graph Coloring algorithm. DASC is part of a bigger project aiming to bring logic programming into a distributed system, started in 2017 by Federico Igne with mASPreduce and continued in 2018 by Pietro Totis with a distributed grounder. In this paper we present a low level implementation of the Graph Coloring algorithm, via the Boost and MPI libraries for C++. Finally, we provide a few results of the very first working version of our tool, at the moment without any strong optimization or heuristic.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Embedding models through the lens of Stable Coloring
Embedding-based approaches find the semantic meaning of tokens in structured data such as natural language, graphs, and even images. To a great degree, these approaches have developed independently in different domains. …
DenoisingScaling Weisfeiler-Leman Expressiveness Analysis to Massive Graphs with GPUs
The stable coloring of the Weisfeiler-Leman (1-WL) test is a cornerstone of Graph Neural Networks because it provides an upper bound to the expressive power of message-passing architectures. Unfortunately, computing it p…
Solving constraint-satisfaction problems with distributed neocortical-like neuronal networks
Finding actions that satisfy the constraints imposed by both external inputs and internal representations is central to decision making. We demonstrate that some important classes of constraint satisfaction problems (CSP…
Decision MakingMathematical ProofsPopulation-based Gradient Descent Weight Learning for Graph Coloring Problems
Graph coloring involves assigning colors to the vertices of a graph such that two vertices linked by an edge receive different colors. Graph coloring problems are general models that are very useful to formulate many rel…
A deep learning guided memetic framework for graph coloring problems
Given an undirected graph $G=(V,E)$ with a set of vertices $V$ and a set of edges $E$, a graph coloring problem involves finding a partition of the vertices into different independent sets. In this paper we present a new…
Deep Learning