析取回答集程序设计结构化测试方法

doi:10.11772/j.issn.1001-9081.2021111891

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (1): 215-220.DOI: 10.11772/j.issn.1001-9081.2021111891

析取回答集程序设计结构化测试方法

杨东, 王以松

贵州大学计算机科学与技术学院，贵阳 550025

收稿日期:2021-11-08 修回日期:2022-04-21 发布日期:2023-01-12
通讯作者: 王以松（1975—），男，贵州思南人，教授，博士，CCF会员，主要研究方向：人工智能、知识表示与推理。yswang@gzu.edu.cn
作者简介:杨东（1987—），男，贵州六盘水人，硕士研究生，CCF会员，主要研究方向：人工智能、知识表示与推理；
基金资助:
国家自然科学基金资助项目（61976065）。

Structural testing methods of disjunctive answer set programs

YANG Dong, WANG Yisong

College of Computer Science and Technology， Guizhou University， Guiyang Guizhou 550025， China

Received:2021-11-08 Revised:2022-04-21 Online:2023-01-12
Contact: WANG Yisong， born in 1975， Ph.D.， professor. His research interests include artificial intelligence， knowledge representation and reasoning.
About author:YANG Dong， born in 1987， M. S. candidate. His research interests include artificial intelligence， knowledge representation and reasoning；
Supported by:
This work is partially supported by National Natural Science Foundation of China （61976065）.

摘要/Abstract

摘要： 针对析取回答集程序的结构化测试基础理论匮乏的问题，系统化地提出析取回答集程序结构化测试覆盖的概念。首先，定义针对析取回答集程序的测试用例，确立析取回答集程序的主要测试实体为程序中的逻辑规则；其次，通过对规则的头、规则的体、规则的集合等不同测试目标构建了规则覆盖、定义覆盖、环覆盖等基本概念来模拟结构化测试中的语句覆盖、分支覆盖等概念；最后，提出了析取回答集程序的测试覆盖率计算公式，并举例说明各种覆盖下的覆盖率计算方法，并讨论了析取回答集程序的部分特殊性质和关键指标。

关键词: 回答集程序设计, 测试理论, 析取回答集程序, 结构化测试方法, 覆盖

Abstract: Focused on the lack of basic theories for structural testing of disjunctive answer set programs， concepts of structured test coverage for disjunctive answer set programs was proposed systematically. Firstly， the test cases of disjunctive answer set programs were defined， and the logic rules in the program were determined to be the main test entities of disjunctive answer set programs. Then， the basic concepts such as rule coverage， definition coverage and loop coverage were constructed for different test targets such as rule header， rule body， and rule set to simulate the concepts such as statement coverage and branch coverage in structural testing. Finally， the calculation formula of test coverage rate for disjunctive answer set programs was proposed， and different coverage calculation methods under different types of coverage were illustrated in samples. At the same time， some special characteristics and key indicators of the disjunctive answer set programs were discussed.

Key words: Answer Set Programming (ASP), testing theory, disjunctive answer set program, structural testing method, coverage

中图分类号:

TP301.6

杨东, 王以松. 析取回答集程序设计结构化测试方法[J]. 计算机应用, 2023, 43(1): 215-220.

YANG Dong, WANG Yisong. Structural testing methods of disjunctive answer set programs[J]. Journal of Computer Applications, 2023, 43(1): 215-220.

参考文献

1 GELFOND M， LIFSCHITZ V. Classical negation in logic pro-grams and deductive databases［J］. New Generation Computing， 1991， 9（3/5）：365-385. 10.1007/bf03037169
2 NGUYEN V， VASILEIOU S L， SON T C， et al. Explainable planning using answer set programming［C］// Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning. California： ijcai.org， 2020： 662-666. 10.24963/kr.2020/66
3 RIZWAN M， PATOGLU V， ERDEM E. Human robot collaborative assembly planning： an answer set programming approach［J］. Theory and Practice of Logic Programming， 2020， 20（6）： 1006-1020. 10.1017/s1471068420000319
4 FALKNER A， FRIEDRICH G， SCHEKOTIHIN K， et al. Industrial applications of answer set programming［J］. KI - Künstliche Intelligenz， 2018， 32（2/3）： 165-176. 10.1007/s13218-018-0548-6
5 IZMIRLIOGLU Y， ERDEM E. Reasoning about cardinal directions between 3-dimensional extended objects using answer set programming［J］. Theory and Practice of Logic Programming， 2020， 20（6）： 942-957. 10.1017/s1471068420000411
6 徐珩僭，王以松，冯仁艳. 一种用于Slater与Kemeny选举求解的ASP方法［J］. 计算机工程， 2019， 45（9）：198-203. 10.19678/j.issn.1000-3428.0052139 XU H J， WANG Y S， FENG R Y. An ASP method for calculating Slater and Kemeny voting［J］. Computer Engineering， 2019， 45（9）：198-203. 10.19678/j.issn.1000-3428.0052139
7 EITER T， FABER W， LEONE N， et al. The diagnosis frontend of the dlv system［J］. AI Communications， 1999， 12（1/2）： 99-111.
8 ERDEM E， WONG M D F. Rectilinear Steiner tree construction using answer set programming［C］// Proceedings of the 2004 International Conference on Logic Programming， LNCS 3132. Berlin： Springer， 2004： 386-399.
9 SUCHAN J， BHATT M， VARADARAJAN S. Out of sight but not out of mind： an answer set programming based online abduction framework for visual sensemaking in autonomous driving［C］// Proceedings of the 28th International Joint Conference on Artificial Intelligence. California： ijcai.org， 2019： 1879-1885. 10.24963/ijcai.2019/260
10 JANHUNEN T， NIEMEL? I， OETSCH J， et al. On testing answer-set programs［C］// Proceedings of the 19th European Conference on Artificial Intelligence. Amsterdam： IOS Press， 2010： 951-956. 10.1007/978-3-642-20895-9_26
11 JANHUNEN T， NIEMEL? I， OETSCH J， et al. Random vs. structure-based testing of answer-set programs： an experimental comparison［C］// Proceedings of the 2011 International Conference on Logic Programming and Nonmonotonic Reasoning， LNCS 6645. Berlin： Springer， 2011： 242-247.
12 OETSCH J， PRISCHINK M， PüHRER J， et al. On the small-scope hypothesis for testing answer-set programs［C］// Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning. Palo Alto， CA： AAAI Press， 2012： 43-53.
13 FEBBRARO O， LEONE N， REALE K， et al. Unit testing in ASPIDE［C］// Proceedings of the 2011 International Conference on Applications of Declarative Programming and Knowledge Management and the 2011 Workshop on Logic Programming， LNCS 7773. Berlin： Springer， 2013： 345-364.
14 BUSONIU P A， OETSCH J， PüHRER J， et al. SeaLion： an eclipse-based IDE for answer-set programming with advanced debugging support［J］. Theory and Practice of Logic Programming， 2013， 13（4/5）： 657-673. 10.1017/s1471068413000410
15 GREβLER A， OETSCH J， TOMPITS H. Harvey： a system for random testing in ASP［C］// Proceedings of the 2017 International Conference on Logic Programming and Nonmonotonic Reasoning， LNCS 10377. Cham： Springer， 2017： 229-235.
16 AMENDOLA G， BEREI T， RICCA F. Testing in ASP： revisited language and programming environment［C］// Proceedings of the 2021 European Conference on Logics in Artificial Intelligence， LNCS 12678. Cham： Springer， 2021： 362-376.
17 LEONE N， RULLO P， SCARCELLO F. Disjunctive stable models： unfounded sets， fixpoint semantics， and computation［J］. Information and Computation， 1997， 135（2）： 69-112. 10.1006/inco.1997.2630
18 GELFOND M， LIFSCHITZ V. The stable model semantics for logic programming［C］// Proceedings of the 5th International Conference and Symposium on Logic Programming. Cambridge： MIT Press， 1988： 1070-1080.
19 张涛. 软件技术基础实验教程［M］. 西安：西北工业大学出版社， 2015：111-112. ZHANG T. Basic Experiment Tutorial of Software Technology［M］. Xi’an： Northwestern Polytechnical University Press， 2015： 111-112
20 蔡立志. 软件测试导论［M］. 北京：清华大学出版社， 2016： 27-89. CAI L Z. Introduction to Software Testing［M］. Beijing： Tsinghua University Press， 2016： 27-89.
21 李香菊，孙丽，谢修娟，等. 软件工程课程设计教程［M］. 北京：北京邮电大学出版社， 2016： 72-90. LI X J， SUN L. XIE X J，et al. Design Tutorial of Software Engineering Course［M］. Beijing： Beijing University of Posts and Telecommunications Press， 2016： 72-90.

[1]	杨乐, 张达敏, 何庆, 邓佳欣, 左锋琴. 改进猎人猎物优化算法在WSN覆盖中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2506-2513.
[2]	徐航, 杨智, 陈性元, 韩冰, 杜学绘. 基于自适应敏感区域变异的覆盖引导模糊测试[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2528-2535.
[3]	韦修喜, 彭茂松, 黄华娟. 基于多策略改进蝴蝶优化算法的无线传感网络节点覆盖优化[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1009-1017.
[4]	郭玲玲, 李志强, 段孟环. 量子近似优化算法在精确覆盖问题中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 849-854.
[5]	黄海新, 于广威, 程寿山, 李春明. 基于改进灰狼优化的桥梁检测爬壁机器人全覆盖路径规划[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 966-971.
[6]	胡中波, 王旭鹏. 求解测试用例自动生成问题的多因子回溯搜索优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1214-1219.
[7]	蒋溢, 伍书平, 胡昆, 龙林波. 基于Lasso和构造性覆盖算法的不均衡数据分类方法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1086-1093.
[8]	杨杰, 张名扬, 芮晓彬, 王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1155-1161.
[9]	张辰, 田甜, 杨秀婷, 巩敦卫. 基于占优关系的并行程序通信覆盖约减方法[J]. 计算机应用, 2021, 41(6): 1741-1747.
[10]	李想, 王卫兵, 尚学达. 指针生成网络和覆盖损失优化的Transformer在生成式文本摘要领域的应用[J]. 计算机应用, 2021, 41(6): 1647-1651.
[11]	郑李萍, 王建强, 张玉召, 董祚帆. 多时空配送任务驱动的无人车队车辆数优化方法[J]. 计算机应用, 2021, 41(5): 1406-1411.
[12]	韩雨涝, 房鼎益. 基于链路交点相对位置信息的轻量级覆盖空洞检测算法[J]. 计算机应用, 2020, 40(9): 2698-2705.
[13]	史佳琦, 谭励, 唐小江, 连晓峰, 王浩宇. 基于小结构体的无线传感器网络部署算法[J]. 计算机应用, 2020, 40(7): 2033-2037.
[14]	陈永红, 郭莉莉, 张士兵, 杨洁. 基于微基站发射功率的异构蜂窝网络能效优化[J]. 计算机应用, 2020, 40(4): 1115-1118.
[15]	徐江峰, 谭玉龙. 基于HBase的多维索引查询机制的优化[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 571-577.

析取回答集程序设计结构化测试方法

Structural testing methods of disjunctive answer set programs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics