Experiments

We have experimented fasp on the benchmark domains: Hamiltonian circuit, N-Queens and graph coloring under AMD server with 4xAMD Opteron 844 (1.8GHz) CPU, 8GB RAM running Fedroa Linux Core 3.0 (X86_64 Edition). and compared its performance with several state-of-art ASP systems, including smodels, cmodels using zChaff 2007.3.12 and clasp. The grounder for these ASP solvers is lparse 1.0.7.

Please note that, no grounding system is available for logic programs with functions that can ground logic programs with functions that are written with variables. (Such a general grounder is under consideration). Thus, we wrote special programs to produce the specific ground logic programs with functions for the above domains. These gadgets are available here as well. Many of the ground logic programs for fasp are also availabe.

In these experiments, we measured the CPU time in seconds of each run. The running times exclude grounding cost of lparse. The size of logic programs are the size of grounded logic programs. In particular, the size of logic programs for FASP(0.4) are encoded with normal logic programs with functions as given in our paper, while in the case of FASP(0.6) they are encoded using function domain statements. For Hamiltonian circuit domain, the encoding for FASP(0.6) is implemented with a special program hc-06.cpp.

In the following demonstrating tables, "--" indicates the run didn't return in two hours; "#" indicates the run happened java.lang.OutOfMemoryError that occurs only to our fasp; "%" indicates the run returned with unknown result. "LFs/Runs" indicates the number of loop formulas being added and the number of calls of CSP solvers respectively, it happens only for Hamiltonian circuit domain.

List of experiments:

1 Hamiltonian circuit

2 N-queens

3 Graph coloring

4 Hamiltonian circuit (for the being translated LPs)

Hamiltonian circuit

There are two encodings for Hamiltonian circuit for ASP systems. One is a normal logic program (Own to Niemela 1999) that is also available in the website of ASSAT. The other is in weight constraint which is available from BENCHMARK PROBLEMS FOR ANSWER SET PROGRAMMING SYSTEMS. We only run the ASP solvers for the former encoding instead of the latter. The version of being used fasp for these expreiments is 0.6 instead of 0.4. These randomly generated graphs are obtained from the website of Cmodels, while the complete graphs are obtained from the website of ASSAT.

Table 1: Hamiltonian circuit

Table 2: Hamiltonian circuit with complete graphs

N-queens

The logic program for N-Queens is obtained from the benchmark suite package of Cmodels.

Table 3: N-Queens

Graph coloring

The logic program for graph-coloring is obtained from the benchmark suite package of Cmodels. While the randomly generated graphs are obtained from the website of ASSAT, where pmvn indicates the graph has m vertices and n edges.

• with four colors

Table 4: Graph coloring with four colors

• with three colors

Table 5: Graph coloring with three colors