Computer Science

Computer Science ›› 2025, Vol. 52 ›› Issue (12): 209-214.doi: 10.11896/jsjkx.241000148

• Artificial Intelligence • Previous Articles     Next Articles

Complexities of Logic Programs with Convex Aggregates

WANG Xianglong, WANG Yisong, XIE Zhongtao   

  1. College of Computer Science and Technology, Guizhou University, State Key Laboratory of Public Big Data, Guiyang 550025, China
  • Received:2024-10-28 Revised:2025-03-03 Online:2025-12-15 Published:2025-12-09
  • About author:WANG Xianglong,born in 2000,postgraduate,is a member of CCF(No.U4668G).His main research interests include knowledge representation and reasoning and artificial intelligence.
    WANG Yisong,born in 1975,Ph.D,professor,is a member of CCF(No.09085M).His main research interests include artificial intelligence,knowledge representation and reasoning,answer set programming and inductive learning in particular.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(61976065,62376066) and Guizhou Science and Technology Program([2022]259).

PDF (PC)

9

Abstract: ASP is a paradigm for descriptive problem solving and is widely used in fields such as planning,diagnosis,scheduling and bioinformatics.To enhance the expressive power of ASP,it has introduced aggregate functions from database systems and proposed semantics such as FLP and SPT.The specific form of abstract constraint stripping aggregation function constraints has become an important tool for studying the semantics and other properties of ASP,and has yielded relevant results regarding the relationships between various answer set semantics of abstract constraint logic programs and complexity issues.The article further investigates the properties of abstract constraint logic with only convex abstract constraint atoms,proving that the existence of FLP answer sets for regular logic programs containing only convex abstract constraint atoms is Σp2-complete,with its cautious reasoning and brave reasoning being Πp2-complete and Σp2-complete,respectively.These complexity results further clarify the expressive power relationships between various types of logic programs,providing new ideas for the design of effective answer set solvers and laying a theoretical foundation for further exploration of ASP applications in solving problems represented by convex abstract constraints.

Key words: Answer set programming, Convex abstract constraint, Answer set semantic, Basic logic program, Computational complexity

CLC Number: 

  • TP301
[1]WANG Y S,LIU H,ZHANG Y,et al.What’s new in the evolu-tion of propositional knowledge bases?[J].Journal of Guizhou University,2024,41(1):1-19.
[2]GELFOND M,LIFSCHITZ V.The stable model semantics for logic programming[C]//Proceedings of the Fifth International Conference and Symposium of Logic Programming.Washington:MIT,1988:1070-1080.
[3]WANG Y S,YOU J H.Answer Set Programming:A System Perspective [J].Chinese Association for Artificial Intelligence,2025,7:22-30.
[4]FANG Y L,ZHAO L Z,QIAN J Y.Existence of Answer Sets of Normal Logic Programs[J].Computer Science,2011,38(12):213-220.
[5]EITER T,GOTTLOB G.On the Computational Cost of Dis-junctive Logic Programming:Propositional Case[J].Annals of Mathematics and Artificial Intelligence,1995,15(3/4):289-323.
[6]CALIMERI F,FABER W,LEONE N,et al.Declarative andComputational Properties of Logic Programs with Aggregates[C] // Proceedings of the 19th International Joint Conference on Artificial Intelligence.Scotland:Professional Book Center,2005:406-411.
[7]MUMICK I S,PIRAHESH H,RAMAKRISHNAN R.TheMagic of Duplicates and Aggregates[C]//16th International Conference on Very Large Data Bases.Queensland:Morgan Kaufmann,1990:264-277.
[8]ALVIANO M,FABER W,GEBSER M.Aggregate Semanticsfor Propositional Answer Set Programs[J].Theory and Practice of Logic Programming,2023,23(1):157-194.
[9]FABER W,PFEIFER G,LEONE N.Semantics and complexity of recursive aggregates in answer set programming[J].Artificial Intelligence,2011,175(1):278-298.
[10]GELFOND M,ZHANG Y L.Vicious Circle Principle,Aggregates,and Formation of Sets in ASP Based Languages[J].Artificial Intelligence,2019,275:28-77.
[11]PELOV N,DENECKER M,BRUYNOOGHE M.Well-founded and stable semantics of logic programs with aggregates[J].Theory and Practice of Logic Programming,2007,7(3):301-353.
[12]DANTSIN E,EITER T,GOTTLOB G,et al.Complexity and Expressive Power of Logic Programming[C]//Proceedings of Twelfth Annual IEEE Conference on Computational Complexity.IEEE,1997:82-101.
[13]FERRARIS P.Logic Programs with Propositional Connectives and Aggregates[J].ACM Transactions on Computational Logic,2011,12(4):25:1-25:40.
[14]LIU L N,PONTELLI E,SON T C,et al.Logic Programs with Abstract Constraint Atoms:the Role of Computations[J].Artificial Intelligence,2010,174(3/4):295-315.
[15]SON T C,PONTELLI E,TU P H.Answer Sets for Logic Programs with Arbitrary Abstract Constraint Atoms[J].Journal of Artificial Intelligence Research,2007,29:353-389.
[16]LIU L N,TRUSZCZYNSKI M.Properties and Applications of Programs with Monotone and Convex Constraints[J].Journal of Artificial Intelligence Research,2006,27:299-334.
[17]SHEN Y D,YOU J H,YUAN L Y.Characterizations of stable model semantics for logic programs with arbitrary constraint atoms[J].Theory and Practice of Logic Programming,2009,9(4):529-564.
[18]FABER W,LEONE N,PFEIFER G.Recursive Aggregates inDisjunctive Logic Programs:Semantics and Complexity[C] // Logics in Artificial Intelligence 9th European Conference.Springer,2004:200-212.
[19]WANG Y S,EITER T,ZHANG Y L,et al.Witnesses for Answer Sets of Logic Programs[J].ACM Transactions on Computational Logic,2023,24(2):1-46.
[20]ALVIANO M,TRIEU L L,SON T C,et al.Explanations forAnswer Set Programming[C]//Proceedings of 39th Internatio-nal Conference on Logic Programming.London:Imperial College London,2023:27-40.
[21]EITER T,GEIBINGER T.Explaining Answer-Set Program-ming with abstract Constraint Atoms[C] //Proceedings of the 32th International Joint Conference on Artificial Intelligence.2023:3193-3202.
[1] CHENG Zhiyu, CHEN Xinglin, WANG Jing, ZHOU Zhongyuan, ZHANG Zhizheng. Retrieval-augmented Generative Intelligence Question Answering Technology Based on Knowledge Graph [J]. Computer Science, 2025, 52(1): 87-93.
[2] HUANG Hua-wei, LI Chun-hua. Security Analysis of A Key Exchange Protocol Based on Tropical Semi-ring [J]. Computer Science, 2022, 49(6A): 571-574.
[3] HAN Jie, CHEN Jun-fen, LI Yan, ZHAN Ze-cong. Self-supervised Deep Clustering Algorithm Based on Self-attention [J]. Computer Science, 2022, 49(3): 134-143.
[4] YOU Ling, GUAN Zhang-jun. Low-complexity Subcarrier Allocation Algorithm for Underwater OFDM Acoustic CommunicationSystems [J]. Computer Science, 2021, 48(6A): 387-391.
[5] ZHU Kai, WU Guo-qing, YUAN Meng-ting. On Hardness of Approximation for Optimized Problem of Synchronizing Partially Specified Deterministic Finite Automata [J]. Computer Science, 2020, 47(5): 14-21.
[6] WU Tian-tian,WANG Jie. Belief Coordination for Multi-agent System Based on Possibilistic Answer Set Programming [J]. Computer Science, 2020, 47(2): 201-205.
[7] YU Jian-jun, WU Chun-ming. Computational Complexity Analysis of Virtual Network Mapping Problem [J]. Computer Science, 2018, 45(11): 87-91.
[8] LU Zhao and ZHU Xiao-shu. Research on Image Processing Algorithm Based on Compressed Sensing [J]. Computer Science, 2017, 44(6): 312-316.
[9] CEN Yue-feng, WANG Wan-liang, YAO Xin-wei, WANG Chao-chao and PAN Tie-qiang. Decision Tree Based Coding Unit Splitting Algorithm for HEVC [J]. Computer Science, 2016, 43(4): 308-312.
[10] LIU Zhen and ZHANG Zhi-zheng. Learning Action Models Described in Action Language B by Combining ILP and ASP [J]. Computer Science, 2015, 42(1): 220-226.
[11] HE Kun,YAO Peng-cheng and LI Li-wen. Complete Algorithm for 2D Rectangular Packing Problem [J]. Computer Science, 2014, 41(8): 55-59.
[12] . Computational Complexity of Probabilistic Inference in Icing Graphical Model [J]. Computer Science, 2013, 40(2): 253-256.
[13] ZHAO Ling-zhong,ZHAI Zhong-yi and QIAN Jun-yan. Framework for Model Checking CSP with Traces of Processes [J]. Computer Science, 2013, 40(11): 181-186.
[14] . Existence of Answer Sets of Normal Logic Programs [J]. Computer Science, 2011, 38(12): 213-220.
[15] . Answer Set Programming Based Verification of Semantic Web Service Composition [J]. Computer Science, 2011, 38(12): 131-134.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.