计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (12): 209-214.doi: 10.11896/jsjkx.241000148

• 人工智能 • 上一篇    下一篇

含凸抽象约束的逻辑程序复杂性

王翔龙, 王以松, 谢仲涛   

  1. 贵州大学计算机科学与技术学院公共大数据国家重点实验室 贵阳 550025
  • 收稿日期:2024-10-28 修回日期:2025-03-03 出版日期:2025-12-15 发布日期:2025-12-09
  • 通讯作者: 王以松(yswang@gzu.edu.cn)
  • 作者简介:(290208655@qq.com)
  • 基金资助:
    国家自然科学基金(62376066,61976065);贵州省科技计划项目(黔科合支撑[2022]一般-259)

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 Published:2025-12-15 Online: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

摘要： 基于回答集语义的逻辑程序(Answer Set Programming,ASP )是描述性问题求解的典范,广泛应用于规划、诊断、调度以及生物信息学等领域。为了增强 ASP 的表达能力,一些工作在ASP 引入了数据库系统中的聚合函数约束,并提出了 SPT,FLP 等语义,抽象约束剥离聚合函数约束的具体形式成为研究 ASP 语义等性质的重要工具,并得到了抽象约束逻辑程序的各种回答集语义之间的关系和复杂性问题等的相关结果。对此,进一步研究了仅含凸抽象约束原子抽象约束逻辑的性质,证明了仅含凸抽象约束原子的正规逻辑程序判定是否存在 FLP 回答集是Σp2完全的,其审慎推理和大胆推理分别是Πp2完全的和Σp2完全的。这些复杂性结果进一步理清了各类逻辑程序间的表达能力关系,为设计有效的回答集求解器提供了新的思路,也为进一步探索ASP在解决用凸抽象约束表示的问题中的应用提供了理论基础。

关键词: 回答集编程, 凸抽象约束, 回答集语义, 基本逻辑程序, 计算复杂性

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

中图分类号: 

  • 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发