Abstract
The extended answer set semantics for simple logic programs, i.e. programs with only classical negation, allows for the defeat of rules to resolve contradictions. In addition, a partial order relation on the program’s rules can be used to deduce a preference relation on its extended answer sets. In this paper, we propose a “quantitative” preference relation that associates a weight with each rule in a program. Intuitively, these weights define the “cost” of defeating a rule. An extended answer set is preferred if it minimizes the sum of the weights of its defeated rules. We characterize the expressiveness of the resulting semantics and show that it can capture negation as failure. Moreover the semantics can be conveniently extended to sequences of weight preferences, without increasing the expressiveness. We illustrate an application of the approach by showing how it can elegantly express subgraph isomorphic approximation problems, a concept often used in intelligence analysis to find specific regions of interest in a large graph of observed activities.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akutsu, T., Halldórsson, M.M.: On the approximation of largest common subtrees and largest common point sets. Theoretical Comp. Science 233(1-2), 33–50 (2000)
Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge Press (2003)
Buccafurri, F., Leone, N., Rullo, P.: Strong and weak constraints in disjunctive datalog. In: Fuhrbach, U., Dix, J., Nerode, A. (eds.) LPNMR 1997. LNCS, vol. 1265, pp. 2–17. Springer, Heidelberg (1997)
Coffman, T., Greenblatt, S., Marcus, S.: Graph-based technologies for intelligence analysis. Communications of the ACM 47(3), 45–47 (2004)
Console, L., Torasso, P.: A spectrum of logical definitions of model-based diagnosis. Computational Intelligence 7(3), 133–141 (1991)
Eiter, T., Faber, W., Leone, N., Pfeifer, G.: The diagnosis frontend of the dlv system. AI Communications 12(1-2), 99–111 (1999)
Eiter, T., Faber, W., Leone, N., Pfeifer, G.: Declarative problemsolving using the dlv system. In: Logic-Based Artificial Intelligence, pp. 79–103 (2000)
Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Proceedings of the Fifth International Conference and Symposium on Logic Programming, pp. 1070–1080. MIT Press, Cambridge (1988)
Heuer, R.J.: Psychology of intelligence analysis. Center for the Study of Intelligence, Central Intelligence Agency (2001)
Lifschitz, V.: Answer set programming and plan generation. Journal of Artificial Intelligence 138(1-2), 39–54 (2002)
Syrjänen, T., Niemelä, I.: The smodels system. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) LPNMR 2001. LNCS (LNAI), vol. 2173, pp. 434–438. Springer, Heidelberg (2001)
Ullman, J.R.: An algorithm for subgraph isomorphism. J. of the ACM 23(1), 31–42 (1976)
Van Nieuwenborgh, D., Heymans, S., Vermeir, D.: On programs with linearly ordered multiple preferences. In: Demoen, B., Lifschitz, V. (eds.) ICLP 2004. LNCS, vol. 3132, pp. 180–194. Springer, Heidelberg (2004)
Van Nieuwenborgh, D., Vermeir, D.: Preferred answer sets for ordered logic programs. In: Flesca, S., Greco, S., Leone, N., Ianni, G. (eds.) JELIA 2002. LNCS (LNAI), vol. 2424, pp. 432–443. Springer, Heidelberg (2002)
Van Nieuwenborgh, D., Vermeir, D.: Ordered diagnosis. In: Y. Vardi, M., Voronkov, A. (eds.) LPAR 2003. LNCS, vol. 2850, pp. 244–258. Springer, Heidelberg (2003)
De Vos, M., Vermeir, D.: Logic programming agents playing games. In: Research and Development in Intelligent Systems XIX (ES 2002). BCS Conference Series, pp. 323–336. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Van Nieuwenborgh, D., Heymans, S., Vermeir, D. (2005). Weighted Answer Sets and Applications in Intelligence Analysis. In: Baader, F., Voronkov, A. (eds) Logic for Programming, Artificial Intelligence, and Reasoning. LPAR 2005. Lecture Notes in Computer Science(), vol 3452. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-32275-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-32275-7_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25236-8
Online ISBN: 978-3-540-32275-7
eBook Packages: Computer ScienceComputer Science (R0)