Reachability is one of the best studied problems in computer science. Instances of the eachability problem occurr, directly or indirectly, in a lot of relevant real world applications, ranging from databases to product configurations and networks. Importantly, the minimality-based semantics of ASP, makes ASP well suited to naturally and efficiently encode Reachability, which is the problem where ASP is much better than SAT and CSP.
Given a directed graph G=(V,E) the solution to the Reachability problem reachable(a,b) determines wether a node b in V is reachable from a node a in
V through a sequence of edges in E. The input is provided by a relation edge(X,Y) where a fact edge(a,b) states that b is directly reachable by and edge from a.
In database terms, determining all pairs of reachable nodes in G amounts to computing the
transitive closure of the relation storing the edges.
In order to make Reachability a decisional problem it is necessary to fix a specific pair of nodes, a and b, and determine wether b is reachable from a. In particular, we require to check wether, on the benchmark instances of the ASP contest, reachable(10380, 10189) is true or not.
Each input graph is represented by the set of its edges.The predicate used to define edges is a binary predicate "edge" where edge(a,b) means that there is a directed edge going from a to b:
Author: Giorgio Terracina
1 - 4 of 4