More Web Proxy on the site http://driver.im/

research-article

Possibilistic nested logic programs and strong equivalence

International Journal of Approximate Reasoning, Volume 59, Issue C

Pages 1 - 19

https://doi.org/10.1016/j.ijar.2015.01.004

Published: 01 April 2015 Publication History

Abstract

In this paper, the class of possibilistic nested logic programs is introduced. These possibilistic logic programs allow us to use nested expressions in the bodies and heads of their rules. By considering a possibilistic nested logic program as a possibilistic theory, a construction of a possibilistic logic programing semantics based on answer sets for nested logic programs and the proof theory of possibilistic logic is defined. In order to define a general method for computing the possibilistic answer sets of a possibilistic nested program, the idea of equivalence between possibilistic nested programs is explored. By considering properties of equivalence between possibilistic programs, a process of transforming a possibilistic nested logic program into a possibilistic disjunctive logic program is defined. Given that our approach is an extension of answer set programming, we also explore the concept of strong equivalence between possibilistic nested logic programs. To this end, we introduce the concept of poss SE-models. Therefore, we show that two possibilistic nested logic programs are strong equivalents whenever they have the same poss SE-models.The expressiveness of the possibilistic nested logic programs is illustrated by a scenario from the medical domain. In particular, we exemplify how possibilistic nested logic programs are expressive enough for capturing medical guidelines which are pervaded by vagueness and qualitative information.

References

[1]

T. Alsinet, C.I. Chesñevar, L. Godo, G.R. Simari, A logic programming framework for possibilistic argumentation: formalization and logical properties, Fuzzy Sets Syst. 159(10) (2008) 1208-1228.

Digital Library

[2]

T. Alsinet, L. Godo, A complete calculus for possibilistic logic programming with fuzzy propositional variables, in: Proceedings of the Sixteen Conference on Uncertainty in Artificial Intelligence, ACM Press, 2000, pp. 1-10.

[3]

American Psychiatric Association, Diagnostic and Statistical Manual of Mental Disorders DSM-IV-TR, (text revision) 4th edition, Amer Psychiatric Pub., 2000, http://www.worldcat.org/isbn/0890420254.

[4]

M. Arenas, L.E. Bertossi, J. Chomicki, Answer sets for consistent query answering in inconsistent databases, Theory Pract. Log. Program. 3(4-5) (2003) 393-424.

Digital Library

[5]

C. Baral, Knowledge Representation, Reasoning and Declarative Problem Solving, Cambridge University Press, Cambridge, 2003.

[6]

C. Baral, M. Gelfond, J.N. Rushton, Probabilistic reasoning with answer sets, Theory Pract. Log. Program. 9(1) (2009) 57-144.

Digital Library

[7]

K. Bauters, S. Schockaert, M.D. Cock, D. Vermeir, Weak and strong disjunction in possibilistic ASP, in: SUM, in: Lecture Notes in Computer Science, vol. 6929, Springer, 2011, pp. 475-488.

[8]

K. Bauters, S. Schockaert, M.D. Cock, D. Vermeir, Characterizing and extending answer set semantics using possibility theory, Theory Pract. Log. Program. 15 (2015) 79-116, http://dx.doi.org/10.1017/S147106841300063X.

[9]

K. Bauters, S. Schockaert, M.D. Cock, D. Vermeir, Semantics for possibilistic answer set programs: uncertain rules versus rules with uncertain conclusions, Int. J. Approx. Reason. 55(2) (2014) 739-761.

Digital Library

[10]

P. Bosc, O. Pivert, H. Prade, A possibilistic logic view of preference queries to an uncertain database, in: IEEE International Conference on Fuzzy Systems, Proceedings, FUZZ-IEEE 2010, Barcelona, Spain, 18-23 July, 2010, IEEE Press, 2010.

[11]

G. Brewka, Answer sets: from constraint programming towards qualitative optimization, in: V. Lifschitz, I. Niemelä (Eds.), Logic Programming and Nonmonotonic Reasoning, 7th International Conference, Proceedings, LPNMR 2004, Fort Lauderdale, FL, USA, January 6-8, 2004, in: Lecture Notes in Computer Science, vol. 2923, Springer, 2004, pp. 34-46.

[12]

R. Confalonieri, J.C. Nieves, Nested preferences in answer set programming, Fundam. Inform. 113(1) (2011) 19-39.

Digital Library

[13]

R. Confalonieri, J.C. Nieves, M. Osorio, J. Vázquez-Salceda, Dealing with explicit preferences and uncertainty in answer set programming, Ann. Math. Artif. Intell. 65(2-3) (2012) 159-198.

Digital Library

[14]

R. Confalonieria, H. Prade, Using possibilistic logic for modeling qualitative decision: answer set programming algorithms, Int. J. Approx. Reason. 55 (2014) 711-738.

Digital Library

[15]

A.R. de Soto, A hierarchical model of a linguistic variable, Inf. Sci. 181(20) (2011) 4394-4408.

Digital Library

[16]

D. Dubois, J. Lang, H. Prade, Possibilistic logic, in: D. Gabbay, C.J. Hogger, J.A. Robinson (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, in: Nonmonotonic Reasoning and Uncertain Reasoning, vol. 3, Oxford University Press, Oxford, 1994, pp. 439-513.

[17]

T. Eiter, G. Gottlob, On the computational cost of disjunctive logic programming: propositional case, Ann. Math. Artif. Intell. 15(3-4) (1995) 289-323.

[18]

O.H. Estrada-Estrada, J.R. Arrazola, M. Osorio, Possibilistic intermediate logic, Int. J. Adv. Intell. Paradig. 4(2) (2012) 149-167.

Digital Library

[19]

M. Fitting, Bilattices and the semantics of logic programming, J. Log. Program. 11(1-2) (1991) 91-116.

Digital Library

[20]

M. Gelfond, V. Lifschitz, The stable model semantics for logic programming, in: R. Kowalski, K. Bowen (Eds.), 5th Conference on Logic Programming, MIT Press, 1988, pp. 1070-1080.

[21]

M. Gelfond, V. Lifschitz, Classical negation in logic programs and disjunctive databases, New Gener. Comput. 9 (1991) 365-385.

Digital Library

[22]

A. HadjAli, S. Kaci, H. Prade, Database preferences queries - a possibilistic logic approach with symbolic priorities, in: Foundations of Information and Knowledge Systems, 5th International Symposium, Proceedings, FoIKS 2008, Pisa, Italy, February 11-15, 2008, in: Lecture Notes in Computer Science, vol. 4932, Springer, 2008, pp. 291-310.

[23]

T. Janhunen, On the effect of default negation on the expressiveness of disjunctive rules, in: LPNMR, in: Lecture Notes in Computer Science, vol. 2173, 2001, pp. 93-106.

[24]

J. Janssen, S. Schockaert, D. Vermeir, M.D. Cock, A core language for fuzzy answer set programming, Int. J. Approx. Reason. 53(4) (2012) 660-692.

Digital Library

[25]

D. Karlsson, Aspects of the use of medical decision-support systems - the role of context in decision support, PhD thesis, Institute of Technology, Linköping University, Linköping, Sweden, 2001.

[26]

M. Kifer, V.S. Subrahmanian, Theory of generalized annotated logic programming and its applications, J. Log. Program. 12(3-4) (1992) 335-367.

Digital Library

[27]

V. Lifschitz, Foundations of logic programming, in: Principles of Knowledge Representation, CSLI Publications, 1996.

Digital Library

[28]

V. Lifschitz, D. Pearce, A. Valverde, Strongly equivalent logic programs, ACM Trans. Comput. Log. 2(4) (2001) 526-541.

Digital Library

[29]

V. Lifschitz, L.R. Tang, H. Turner, Nested expressions in logic programs, Ann. Math. Artif. Intell. 25(3-4) (1999) 369-389.

Digital Library

[30]

H. Lindgren, Decision support in dementia care - developing systems for interaction reasoning, PhD thesis, Department of Computing Sciences, Umeå University, Umeå, Sweden, 2007.

[31]

H. Lindgren, Towards personalized decision support in the dementia domain based on clinical practice guidelines, User Model. User-Adapt. Interact. 21(4-5) (2011) 377-406.

Digital Library

[32]

H. Lindgren, L. Lundin-Olsson, P. Pohl, M. Sandlund, End users transforming experiences into formal information and process models for personalised health interventions, in: e-Health - For Continuity of Care - Proceedings of MIE2014, the 25th European Medical Informatics Conference, Istanbul, Turkey, August 31-September 3, 2014, in: Studies in Health Technology and Informatics, vol. 205, IOS Press, 2014, pp. 378-382.

[33]

H. Lindgren, P. Winnberg, Evaluation of a semantic web application for collaborative knowledge building in the dementia domain, in: eHealth, 2010, pp. 62-69.

[34]

J. Liu, W. Li, S. Chen, Y. Xu, An axiomatizable logical foundation for lattice-ordered qualitative linguistic approach for reasoning with words, Inf. Sci. 263 (2014) 110-125.

Digital Library

[35]

P. Nicolas, L. Garcia, I. Stéphan, C. Lefèvre, Possibilistic uncertainty handling for answer set programming, Ann. Math. Artif. Intell. 47(1-2) (2006) 139-181.

Digital Library

[36]

J.C. Nieves, H. Lindgren, Possibilistic nested logic programs, in: A. Dovier, V.S. Costa (Eds.), Technical Communications of the 28th International Conference on Logic Programming (ICLP'12), in: Leibniz International Proceedings in Informatics (LIPIcs), vol. 17, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2012, pp. 267-276, http://drops.dagstuhl.de/opus/volltexte/2012/3628.

[37]

J.C. Nieves, M. Osorio, U. Cortés, Semantics for possibilistic disjunctive programs, Theory Pract. Log. Program. 13(1) (2013) 33-70.

Digital Library

[38]

J. O'Brien, D. Ames, A. Burns (Eds.), Dementia, Arnold, 2000.

[39]

M. Osorio, J.A.N. Pérez, J. Arrazola, Applications of intuitionistic logic in answer set programming, Theory Pract. Log. Program. 4(3) (2004) 325-354.

Digital Library

[40]

D. Pearce, Stable inference as intuitionistic validity, J. Log. Program. 38(1) (1999) 79-91.

[41]

D. Pearce, V. Sarsakov, T. Schaub, H. Tompits, S. Woltran, A polynomial translation of logic programs with nested expressions into disjunctive logic programs: preliminary report, in: ICLP, in: Lecture Notes in Computer Science, vol. 2401, Springer, 2002, pp. 405-420.

[42]

H. Prade, Advances in data management, in: Current Research Trends in Possibilistic Logic: Multiple Agent Reasoning, Preference Representation, and Uncertain Databases, Springer, Berlin/Heidelberg, 2009.

[43]

V. Sarsakov, T. Schaub, H. Tompits, S. Woltran, NLP: a compiler for nested logic programming, in: LPNMR, in: Lecture Notes in Computer Science, Springer, 2004, pp. 361-364.

[44]

H. Turner, Strong equivalence made easy: nested expressions and weight constraints, Theory Pract. Log. Program. 3(4-5) (2003) 609-622.

Digital Library

[45]

D. van Dalen, Logic and Structure, 3rd edition, Springer-Verlag, Berlin, 1994.

[46]

D. Van-Nieuwenborgh, M.D. Cock, D. Vermeir, An introduction to fuzzy answer set programming, Ann. Math. Artif. Intell. 50(3-4) (2007) 363-388.

Digital Library

Cited By

Yan CLindgren HNieves J(2018)A dialogue-based approach for dealing with uncertain and conflicting information in medical diagnosisAutonomous Agents and Multi-Agent Systems10.5555/3288249.328826332:6(861-885)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288249.3288263

Possibilistic nested logic programs and strong equivalence
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
2. Theory of computation
  1. Logic
  2. Semantics and reasoning

Recommendations

Strong equivalence of logic programs under the infinite-valued semantics

We consider the notion of strong equivalence [V. Lifschitz, D. Pearce, A. Valverde, Strongly equivalent logic programs, ACM Transactions on Computational Logic 2 (4) (2001) 526-541] of normal propositional logic programs under the infinite-valued ...
Nested epistemic logic programs
LPNMR'05: Proceedings of the 8th international conference on Logic Programming and Nonmonotonic Reasoning

Nested logic programs and epistemic logic programs are two important extensions of answer set programming. However, the relationship between these two formalisms is rarely explored. In this paper we first introduce the epistemic HT-logic, and then ...
Characterising equilibrium logic and nested logic programs: Reductions and complexity1,2

Equilibrium logic is an approach to non-monotonic reasoning that extends the stable-model and answer-set semantics for logic programs. In particular, it includes the general case of nested logic programs, where arbitrary Boolean combinations are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Approximate Reasoning

International Journal of Approximate Reasoning Volume 59, Issue C

April 2015

105 pages

ISSN:0888-613X

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 April 2015

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yan CLindgren HNieves J(2018)A dialogue-based approach for dealing with uncertain and conflicting information in medical diagnosisAutonomous Agents and Multi-Agent Systems10.5555/3288249.328826332:6(861-885)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288249.3288263

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents