Eliminating Disjunctions in Answer Set Programming by Restricted Unfolding
Authors: Jianmin Ji, Hai Wan, Kewen Wang, Zhe Wang, Chuhan Zhang, Jiangtao Xu
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The experiment shows that the algorithm is efficient for some disjunctive programs.6 Some Experiments We have implemented a program1 for rewriting a DLP P to an NLP P n, where P n is a simplified program from sh(remove(P, HC(P))) by removing redundancies like rules r with head(r) \ body+(r) 6= ; or body+(r) \ body (r) 6= ;. By Theorem 4, AS(P) = AS(P n). If the size of the NLP P n is similar to the size of the DLP P, it will be more efficient to compute answer sets of P n using NLP solvers than to compute answer sets of P using DLP solvers. To corroborate this observation, we tested our program on some benchmarks constructed from Niemel a s [1999] encoding H of the Hamiltonian Circuit (HC) problem. |
| Researcher Affiliation | Academia | Jianmin Ji1, Hai Wan2 , Kewen Wang3, Zhe Wang3, Chuhan Zhang2, and Jiangtao Xu2 1School of Computer Science and Technology, University of Science and Technology of China, Hefei, China jianmin@ustc.edu.cn 2School of Data and Computer Science, Sun Yat-sen University, Guangzhou, China wanhai@mail.sysu.edu.cn 3School of Information and Communication Technology, Griffith University, Griffith, Australia {k.wang,zhe.wang}@griffith.edu.au |
| Pseudocode | Yes | Algorithm 1: Computing answer sets of a DLP 1 H := HC( ); 2 as := AS(sh( )); 3 output as; // current computed answer sets of 4 for each a 2 H do 5 := remove( , a); 6 as := AS(sh( )); 7 output as; 8 return as; |
| Open Source Code | Yes | 1Our implementation is available on the web http://ss.sysu.edu.cn/%7ewh/dlp2nlp.html. |
| Open Datasets | Yes | To corroborate this observation, we tested our program on some benchmarks constructed from Niemel a s [1999] encoding H of the Hamiltonian Circuit (HC) problem. [Niemel a, 1999] I. Niemel a. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence, 25(3):241 273, 1999. |
| Dataset Splits | No | The paper mentions using "benchmarks constructed from Niemel a s [1999] encoding H of the Hamiltonian Circuit (HC) problem" and "rand m k(t) stands for a class of randomly generated t graphs". However, it does not provide specific dataset split information (percentages, sample counts, or explicit splitting methodology) for training, validation, or testing. |
| Hardware Specification | Yes | 2Our experiments were done on an Intel(R) Core(TM) i7-2600 3.40GHz CPU and 32GB RAM. |
| Software Dependencies | Yes | 3The modern versions of clasp have built-in support for DLPs. http://www.cs.uni-potsdam.de/clasp/ clasp3 (version 3.1.4)4http://www.cs.utexas.edu/users/tag/cmodels/ cmodels4 (version 3.8.5) |
| Experiment Setup | Yes | Specifically, we constructed programs of the form Q = Q0 [H [G where H is Niemel a s encoding for the HC problem, G is the encoding of the graph for a given HC instance, and the program Q0 is given as the following: a _ b reached(1). a b. b a. where reached(1) is an atom in H and a, b are new atoms not appearing in H. In Table 1, we compare the running times of computing an answer set of Q and Qn using solvers clasp and cmodels. In the table, rand m k(t) stands for a class of randomly generated t graphs with m vertexes and k arcs. |