• Articles • Previous Articles     Next Articles

Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction

Xi-Shun Zhao and Yu-Ping Shen   

  1. Institute of Logic and Cognition, Sun Yat-Sen University, Guangzhou 510275, China
  • Received:2006-05-16 Revised:2007-02-08 Online:2007-07-10 Published:2007-07-10

In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction. That is, taking perfect model semantics and stable model semantic as an example, any logic program $P$ can be transformed in polynomial time to another logic program $P'$ such that perfect models (resp. stable models) of $P$ 1-1 correspond to stable models (resp. perfect models) of $P'$, and the correspondence can be computed also in polynomial time. However, the minimal model semantics has weaker expressiveness than other mentioned semantics, otherwise, the polynomial hierarchy would collapse to NP.

Key words: information unit; script; synchronization; XYZ System; temporal logic; multimedia;

[1] Gogic G, Kautz H, Papadimitriou C, Selman B. The comparative linguistics of knowledge representation. In -\it Proc. Int. Joint Conf. Artificial Intelligence $($IJCAI'95$)$}, Montreal, Canada, 1995, pp.862$\sim$869.

[2] Janhunen T, Oikarinen E. Capturing parallel circumscription with disjunctive logic programs. In -\it Proc. Logics in Artificial Intelligence $($JELIA'04$)$}, Lisbon, Portugal, 2004, pp.134$\sim$146.

[3] Xishun Zhao, H Kleine B\"-u}ning. Model-equivalent reductions. -\it Lecture Notes in Computer Science}, Springer, 2005, 3569: 355$\sim$370.

[4] Plaisted D, Greenbaum S. A structure preserving clause form transformation. -\it Journal of Symbolic Computation}, 1986, 2(3): 293$\sim$304.

[5] Gelfond M, Przymusinska H, Ptzymusinki T. On the relationship between circumscription and negation as failure. -\it Artificial Intelligence}, 1989, 38(1): 75$\sim$94.

[6] Lifschitz V. Circumscription. -Handbook of Logic in AI and Logic Programming}, Oxford University Press, 1994, 3: 298$\sim$352.

[7] Przymusinski T. On the Declarative and Procedural Semantics of Stratified Deductive Databases. -Foundation of Deductive Databases and Logic Programming}, Morgan Kaufman, 1988, pp.193$\sim$216.

[8] Przymusinski T. Stable models for disjunctive programs. -\it New Generation Computing}, 1991, 9(3/4): 401$\sim$424.

[9] Gelfond M, Lifschitz V. The stable model semantics for logic programming. In -\it Proc. the 5th Int. Conf. Logic Programming}, Seattle, USA, The MIT Press, 1988, pp.1070$\sim$1080.

[10]Gelfond M, Lifschitz V. Classical negation in logic programs and disjunctive database. -\it New Generation Computing}, 1991, 9(3/4): 365$\sim$386.

[11] Ferraris P, Lee J, Lifschitz V. A new perspective on stable models. In -\it Proc. Int. Joint Conf. Artificial Intelligence $($IJCAI'07$)$}, Hyderabad, India, 2007, pp.372$\sim$379.

[12] Ferraris P, Lee J, Lifschitz V. A generalization of the Lin-Zhao theorem. -\it Annals of Mathematics and Artificial Intelligence}, to appear.

[13] Lin F, Zhou Y. From answer set programming to circumscription via logic of GK. In -\it Proc. International Joint Conference on Artificial Intelligence $($IJCAI'07$)$}, Hyderabad, India, 2007, pp.441$\sim$446.

[14] Lin F. A study of nonmonotonic reasoning
[Dissertation]. Stanford University, 1991.

[15] Gottlob G. The complexity results for non-monotonic logics. -\it J. Logic and Computation}, 1992, 2(3): 397$\sim$425.

[16] Ben-Eliyahu R, Dechter R. Propositional semantics for disjunctive logic programs. -\it Annals of Mathematics and Artificial Intelligence}, 1994, 12(1/2): 53$\sim$87.

[17] Eiter T, Gottlob G. On the computational cost of disjunctive logic programming: Propositional case. -\it Annals of Mathematics and Artificial Intelligence}, 1995, 15(3/4): 289$\sim$323.

[18]Egly U, Eiter T, Tompits H, Woltran S. Solving advanced reasoning tasks using quantified Boolean formulas. In -\it Proc. National Conference on Artificial Intelligence $($AAAI'2000$)$}, Austin, USA, 2000, pp.417$\sim$422.

[19] Imielinski T. Results on translating defaults to circumscription. -\it Artificial Intelligence}, 1987, 32(1): 131$\sim$146.

[20] Janhunen T. On the intertranslatability of non-monotonic logics. -\it Annals of Mathematics and Artificial Intelligence}, 1999, 27(1$\sim$4): 79$\sim$128.

[21] Janhunen T, Niemela I, Seipel D \it et al. \rm Unfolding partiality and disjunctions in stable model semantics. -\it ACM Trans. Computational Logic}, 2006, 7(1): 1$\sim$37.

[22] Lin F, Zhao Y. ASSAT: Computing answer sets of a logic program by SAT solvers. -\it Artificial Intelligence}, 2004, 157(1/2): 115$\sim$137.

[23] Pearce D, Tompits H, Woltran S. Encodings for equilibrium logic and logic programs with nested expressions. -\it Lecture Notes in Artificial Intelligence}, 2001, 2258: 306$\sim$320.

[24] Leone N, Pfeifer G, Faber W \it et al. \rm The DLV system for knowledge representation and reasoning. -\it ACM Trans. Computational Logic}, 2006, 7(3): 499$\sim$562.

[25] McCarthy J. Circumscription --A form of non-monotonic reasoning. -\it Artificial Intelligence}, 1986, -13}(1/2): 89$\sim$116.

[26] H Kleine B\"-u}ning, T Lettmann. Propositional Logic: Deduction and Algorithms. Cambridge University Press, 1999.

[27]Tseitin G S. On the complexity of derivation in propositional calculus. -\it Studies in Constructive Mathematics and Mathematical Logic}, Part II, Silenko A O (ed.), 1970, pp.115$\sim$125.

[28] Lin F, Shoham Y. A logic of knowledge of justified assumptions. -\it Artificial Intelligence}, 1992, 57(2/3): 271$\sim$289.

[29] Eiter T, Leone N, Sacc\`-a} D. Expressive power and complexity of partial models for disjunctive databases. -\it Theoretical Computer Science}, 1998, 206(1/2): 181$\sim$218.

[30] Jia-Huai You, Li-Yan Yuan. On the equivalence semantics for normal logic programs. -\it J. Logic Programming}, 1995, 22(3): 211$\sim$222.
[1] Zeynep Banu Ozger, Nurgul Yuzbasioglu Uslu. An Effective Discrete Artificial Bee Colony Based SPARQL Query Path Optimization by Reordering Triples [J]. Journal of Computer Science and Technology, 2021, 36(2): 445-462.
[2] Wan-Wei Liu, Fu Song, Tang-Hao-Ran Zhang, Ji Wang. Verifying ReLU Neural Networks from a Model Checking Perspective [J]. Journal of Computer Science and Technology, 2020, 35(6): 1365-1381.
[3] Hong Fang, Bo Zhao, Xiao-Wang Zhang, Xuan-Xing Yang. A United Framework for Large-Scale Resource Description Framework Stream Processing [J]. Journal of Computer Science and Technology, 2019, 34(4): 762-774.
[4] Song Liu, Yuan-Zhen Cui, Nian-Jun Zou, Wen-Hao Zhu, Dong Zhang, Wei-Guo Wu. Revisiting the Parallel Strategy for DOACROSS Loops [J]. Journal of Computer Science and Technology, 2019, 34(2): 456-475.
[5] Pedro Luis Mateo Navarro, Gregorio Martínez Pérez, Member, IEEE, Diego Sevilla Ruiz. A Script-Based Prototyping Framework to Boost Agile-UX Developments [J]. , 2016, 31(6): 1246-1261.
[6] Yuan-Chao Xu, Hu Wan, Ke-Ni Qiu, Tao Li, Wei-Gong Zhang. Reducing Synchronization Cost for Single-Level Store in Mobile Systems [J]. , 2016, 31(4): 836-848.
[7] Zeinab Hmedeh, Harry Kourdounakis, Vassilis Christophides, Cédric du Mouza, et al. Content-Based Publish/Subscribe System for Web Syndication [J]. , 2016, 31(2): 359-380.
[8] Fang Zheng, Hong-Liang Li, Hui Lv, Feng Guo, Xiao-Hong Xu, Xiang-Hui Xie. Cooperative Computing Techniques for a Deeply Fused and Heterogeneous Many-Core Processor Architecture [J]. , 2015, 30(1): 145-162.
[9] Yuan-Yuan Xu, Ce Zhu, and Lu Yu. Multipath Routing of Multiple Description Coded Images in Wireless Networks [J]. , 2014, 29(4): 576-588.
[10] Wen Qu, Kai-Song Song, Yi-Fei Zhang, Shi Feng, Da-Ling Wang, and Ge Yu. A Novel Approach Based on Multi-View Content Analysis and SemiSupervised Enrichment for Movie Recommendation [J]. , 2013, 28(5): 776-787.
[11] Yi Huang, Chao Tang, Hong-Liang Duan, Yi-Qing Zhou, Man-Li Qian, and Liang Huang. Efficient Time Synchronization Approach for Wireless Communication Systems on GPP-Based Software-Defined Radio Platform [J]. , 2013, 28(3): 429-436.
[12] Benjamín Sahelices, Agustín de Dios, Pablo Ibáñez, Member, IEEE, Víctor Viñals-Yúfera, Member, ACM, IEEE, and José María Llabería. Efficient Handling of Lock Hand-off in DSM Multiprocessors with Buffering Coherence Controllers [J]. , 2012, 27(1): 75-91.
[13] He-Fei Ling (凌贺飞), Senior Member, CCF, Member, ACM, IEEE, Li-YunWang (王丽云), Ling-Yu Yan (严灵毓), Fu-Hao Zou (邹复好), and Zheng-Ding Lu (卢正鼎). PM-DFT: A New Local Invariant Descriptor Towards Image Copy Detection [J]. , 2011, 26(3): 558-567.
[14] Hui-Min Cui(崔慧敏), Lei Wang(王 蕾), Dong-Rui Fan(范东睿), Member CCF, IEEE and Xiao-Bing Feng(冯晓兵). Landing Stencil Code on Godson-T [J]. , 2010, 25(4): 886-894.
[15] Jian-Wei Xu, Student Member, CCF, Ming-Yu Chen, Member, CCF, ACM, IEEE, Gui Zheng, Zheng Cao, Hui-Wei Lv, and Ning-Hui Sun, Senior Member, CCF, Member, IEEE. SimK: A Large-Scale Parallel Simulation Engine [J]. , 2009, 24(6): 1048-1060.
Full text



[1] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[5] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[6] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[7] Jin Zhiquan; Liu Chengfei; Sun Zhongxiu; Zhou Xiaofang; Chen Peipei; Gu Jianming;. Design and Implementation of a Heterogeneous Distributed Database System[J]. , 1990, 5(4): 363 -373 .
[8] Han Jianchao; Shi Zhongzhi;. Formalizing Default Reasoning[J]. , 1990, 5(4): 374 -378 .
[9] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[10] Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved