Conference Paper
BibTex RIS Cite

IMSD: Interactive Methods for Finding Similar or Diverse Answer Sets

Year 2021, Volume: 12 , 85 - 94, 31.12.2021

Asmaa Afeefı

https://doi.org/10.55549/epstem.1038379

Abstract

Answer set programming (ASP) is a modeling language in knowledge representation, rooted in Logic Programming and Nonmonotonic Reasoning, which has been gaining increasing attention during the last years. In recent years, many of the researchers developed integrated development environments (IDE) for ASP programs including editors and debuggers. Other researchers focused on analyzing the answer sets, they introduced offline and online methods to find specific solutions of a given problem in answer set programming in different approaches such as phylogeny reconstruction. However, with an enormous number of answer sets could be available, the user is not interested in all of them. Thus, a navigation of the search space could be a solution to help the user to access the specific answer sets. To this end, we aim at finding similar/diverse solutions of the answer sets with a new method. The intuition behind this navigation is to make the search faster than other methods and explore information that is related to the user’s query. Afterward, we implement a tool performing the above approach in order to simplify the search task and show the applicability and effectiveness of our method. We conclude by testing the performance of the proposed tool into a real-world example of ASP programs.

Keywords

Answer set programming Navigation approach Diversity Similarity.

References

  • Afeefi, A. (2019, April). NavAS: Navigation Approaches for Answer Sets. In 2019 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT) (pp. 79-84). IEEE. https://doi.org/10.1109/JEEIT.2019.8717370
  • Ambroz, T., Charwat, G., Jusits, A., Wallner, J. P., & Woltran, S. (2013, September). ARVis: Visualizing relations between answer sets. In International Conference on Logic Programming and Nonmonotonic Reasoning (pp. 73-78). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40564-8_8
  • Baum, D. (2004). Finding All Maximal Cliques of a Family of Induced Subgraphs., 1–15. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.358
  • Bron, C., & Kerbosch, J. (1973). Algorithm 457: Finding all cliques in an undirected graph, Community. ACM, 16(9), 575-577. https://doi.org/10.1145/362342.362367
  • Busoniu, P. A., Oetsch, J., Pührer, J., Skočovský, P., & Tompits, H. (2013). SeaLion: An eclipse-based IDE for answer-set programming with advanced debugging support. Theory and Practice of Logic Programming, 13(4–5). https://doi.org/10.1017/S1471068413000410
  • Computing the Stable Model Semantics. (n.d.). Retrieved June 30, 2021, from http://www.tcs.hut.fi/Software/smodels/
  • Das, A., Sanei-Mehri, S.-V., & Tirthapura, S. (2020). Shared-memory parallel maximal Clique Enumeration from static and dynamic graphs. ACM Transactions on Parallel Computing, 7(1), 1–28.
  • Deng, F., Siersdorfer, S., & Zerr, S. (2012). Efficient Jaccard-based diversity analysis of large document collections. ACM International Conference Proceeding Series. https://doi.org/10.1145/2396761.2398445
  • Eiter, T., Erdem, E., Erdoǧan, H., & Fink, M. (2009). Finding similar or diverse solutions in answer set programming. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5649 LNCS. https://doi.org/10.1007/978-3-642-02846-5_29
  • Erdem, E., Gelfond, M., & Leone, N. (2016). Applications of answer set programming. AI Magazine, 37(3), 53–68.
  • Everardo, F., & Osorio, M. (2020). Towards an answer set programming methodology for constructing programs following a semi-automatic approach – extended and revised version. Electronic Notes in Theoretical Computer Science, 354, 29–44.
  • Fakecineaste : How to Calculate the Hamming Code. (n.d.). Retrieved June 30, 2021, from http://fakecineaste.blogspot.com/2012/11/how-to-calculate-hamming-code.html
  • Fandinno, J., & Schulz, C. (2019). Answering the “why” in answer set programming - A survey of explanation approaches. Theory and Practice of Logic Programming, 19(2). https://doi.org/10.1017/S1471068418000534
  • Febbraro, O., Reale, K., & Ricca, F. (2011). ASPIDE: Integrated development environment for answer set programming. In Logic Programming and Nonmonotonic Reasoning (pp. 317–330). Berlin, Heidelberg: Springer Berlin Heidelberg.
  • Gebser, M., Kaminski, R., Kaufmann, B., & Schaub, T. (2014). Clingo = ASP + Control: Preliminary Report. 1. http://arxiv.org/abs/1405.3694
  • Güven, Ç., & Atzmueller, M. (2019). Applying answer set programming for knowledge-based link prediction on social interaction networks. Frontiers in Big Data, 2, 15.
  • iGROM download | SourceForge.net. (n.d.). Retrieved June 30, 2021, from https://sourceforge.net/projects/igrom/
  • Li, Y., Shao, Z., Yu, D., Liao, X., & Jin, H. (2019). Fast maximal clique enumeration for real-world graphs. In Database Systems for Advanced Applications (pp. 641–658). Cham: Springer International Publishing.
  • Makino, K., & Uno, T. (2004). New algorithms for enumerating all maximal cliques. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3111. https://doi.org/10.1007/978-3-540-27810-8_23
  • Marcopoulos, E., Reotutar, C., & Zhang, Y. (2017). An Online Development Environment for Answer Set Programming. 1. http://www.math.ttu.edu/texprep/
  • Niemelä, I., & Simons, P. (n.d.). Smodels: An implementation of the stable model and well-founded semantics for normal lp”.
  • Son, T. C., & Balduccini, M. (2018). Answer set planning in single- and multi-agent environments. KI - Künstliche Intelligenz, 32(2–3), 133–141.
  • Sureshkumar, A., De Vos, M., Brain, M., & Fitch, J. (2007). APE: An AnsProlog* environment. CEUR Workshop Proceedings, 281.
  • Zhu, Y., & Truszczynski, M. (2013). On optimal solutions of answer set optimization problems. In Logic Programming and Nonmonotonic Reasoning (pp. 556–568). Berlin, Heidelberg: Springer Berlin Heidelberg.

Year 2021, Volume: 12 , 85 - 94, 31.12.2021

Asmaa Afeefı

https://doi.org/10.55549/epstem.1038379

Abstract

References

  • Afeefi, A. (2019, April). NavAS: Navigation Approaches for Answer Sets. In 2019 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT) (pp. 79-84). IEEE. https://doi.org/10.1109/JEEIT.2019.8717370
  • Ambroz, T., Charwat, G., Jusits, A., Wallner, J. P., & Woltran, S. (2013, September). ARVis: Visualizing relations between answer sets. In International Conference on Logic Programming and Nonmonotonic Reasoning (pp. 73-78). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40564-8_8
  • Baum, D. (2004). Finding All Maximal Cliques of a Family of Induced Subgraphs., 1–15. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.358
  • Bron, C., & Kerbosch, J. (1973). Algorithm 457: Finding all cliques in an undirected graph, Community. ACM, 16(9), 575-577. https://doi.org/10.1145/362342.362367
  • Busoniu, P. A., Oetsch, J., Pührer, J., Skočovský, P., & Tompits, H. (2013). SeaLion: An eclipse-based IDE for answer-set programming with advanced debugging support. Theory and Practice of Logic Programming, 13(4–5). https://doi.org/10.1017/S1471068413000410
  • Computing the Stable Model Semantics. (n.d.). Retrieved June 30, 2021, from http://www.tcs.hut.fi/Software/smodels/
  • Das, A., Sanei-Mehri, S.-V., & Tirthapura, S. (2020). Shared-memory parallel maximal Clique Enumeration from static and dynamic graphs. ACM Transactions on Parallel Computing, 7(1), 1–28.
  • Deng, F., Siersdorfer, S., & Zerr, S. (2012). Efficient Jaccard-based diversity analysis of large document collections. ACM International Conference Proceeding Series. https://doi.org/10.1145/2396761.2398445
  • Eiter, T., Erdem, E., Erdoǧan, H., & Fink, M. (2009). Finding similar or diverse solutions in answer set programming. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5649 LNCS. https://doi.org/10.1007/978-3-642-02846-5_29
  • Erdem, E., Gelfond, M., & Leone, N. (2016). Applications of answer set programming. AI Magazine, 37(3), 53–68.
  • Everardo, F., & Osorio, M. (2020). Towards an answer set programming methodology for constructing programs following a semi-automatic approach – extended and revised version. Electronic Notes in Theoretical Computer Science, 354, 29–44.
  • Fakecineaste : How to Calculate the Hamming Code. (n.d.). Retrieved June 30, 2021, from http://fakecineaste.blogspot.com/2012/11/how-to-calculate-hamming-code.html
  • Fandinno, J., & Schulz, C. (2019). Answering the “why” in answer set programming - A survey of explanation approaches. Theory and Practice of Logic Programming, 19(2). https://doi.org/10.1017/S1471068418000534
  • Febbraro, O., Reale, K., & Ricca, F. (2011). ASPIDE: Integrated development environment for answer set programming. In Logic Programming and Nonmonotonic Reasoning (pp. 317–330). Berlin, Heidelberg: Springer Berlin Heidelberg.
  • Gebser, M., Kaminski, R., Kaufmann, B., & Schaub, T. (2014). Clingo = ASP + Control: Preliminary Report. 1. http://arxiv.org/abs/1405.3694
  • Güven, Ç., & Atzmueller, M. (2019). Applying answer set programming for knowledge-based link prediction on social interaction networks. Frontiers in Big Data, 2, 15.
  • iGROM download | SourceForge.net. (n.d.). Retrieved June 30, 2021, from https://sourceforge.net/projects/igrom/
  • Li, Y., Shao, Z., Yu, D., Liao, X., & Jin, H. (2019). Fast maximal clique enumeration for real-world graphs. In Database Systems for Advanced Applications (pp. 641–658). Cham: Springer International Publishing.
  • Makino, K., & Uno, T. (2004). New algorithms for enumerating all maximal cliques. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3111. https://doi.org/10.1007/978-3-540-27810-8_23
  • Marcopoulos, E., Reotutar, C., & Zhang, Y. (2017). An Online Development Environment for Answer Set Programming. 1. http://www.math.ttu.edu/texprep/
  • Niemelä, I., & Simons, P. (n.d.). Smodels: An implementation of the stable model and well-founded semantics for normal lp”.
  • Son, T. C., & Balduccini, M. (2018). Answer set planning in single- and multi-agent environments. KI - Künstliche Intelligenz, 32(2–3), 133–141.
  • Sureshkumar, A., De Vos, M., Brain, M., & Fitch, J. (2007). APE: An AnsProlog* environment. CEUR Workshop Proceedings, 281.
  • Zhu, Y., & Truszczynski, M. (2013). On optimal solutions of answer set optimization problems. In Logic Programming and Nonmonotonic Reasoning (pp. 556–568). Berlin, Heidelberg: Springer Berlin Heidelberg.
There are 24 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Asmaa Afeefı

Early Pub Date September 5, 2021
Publication Date December 31, 2021
Published in Issue Year 2021Volume: 12

Cite

APA Afeefı, A. (2021). IMSD: Interactive Methods for Finding Similar or Diverse Answer Sets. The Eurasia Proceedings of Science Technology Engineering and Mathematics, 12, 85-94. https://doi.org/10.55549/epstem.1038379
Creative Commons License