| Class Tree | |
|---|---|
| Description |
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. Input format: 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: edge(1,3). edge(4,2). Author: Giorgio Terracina |
| Submitter | Martin Gebser |
| Compatible Encodings | |
| Output Predicates |
|
| Instances 0 |
|
Expand All
Collapse All
