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

article

Propositional defeasible logic has linear complexity

Author:

Michael J. MaherAuthors Info & Claims

Theory and Practice of Logic Programming, Volume 1, Issue 6

Pages 691 - 711

https://doi.org/10.1017/S1471068401001168

Published: 01 November 2001 Publication History

Abstract

Defeasible logic is a rule-based nonmonotonic logic, with both strict and defeasible rules, and a priority relation on rules. We show that inference in the propositional form of the logic can be performed in linear time. This contrasts markedly with most other propositional nonmonotonic logics, in which inference is intractable.

References

[1]

Antoniou, G., Billington, D., Governatori, G. and Maher, M. J. (2000) A flexible framework for defeasible logics. Proc. American National Conference on Artificial Intelligence (AAAI-00), AAAI/MIT Press, pp. 405-410.

[2]

Antoniou, G., Billington, D., Governatori, G. and Maher, M. J. (2001) Representation results for defeasible logic. ACM Transactions on Computational Logic, 2: 255-287.

Digital Library

[3]

Antoniou, G., Billington, D. and Maher, M. J. (1998) Normal forms for defeasible logic. Proc. 1998 Joint International Conference and Symposium on Logic Programming, MIT Press, pp. 160-174.

[4]

Antoniou, G., Billington, D. and Maher, M. J. (1999) On the analysis of regulations using defeasible rules. Proc. 32nd Hawaii International Conference on Systems Science.

[5]

Antoniou, G., Maher, M. J. and Billington, D. (2000) Defeasible logic versus logic programming without negation as failure. Journal of Logic Programming, 41(1): 45-57.

[6]

Billington, D. (1993) Defeasible logic is stable. Journal of Logic and Computation, 3: 370-400.

[7]

Billington, D., de Coster, K. and Nute, D. (1990) A modular translation from defeasible nets to defeasible logic. Journal of Experimental and Theoretical Artificial Intelligence, 2: 151-177.

[8]

Billington, D. and Rock, A. (2001) Propositional plausible logic: introduction and implementation. Studia Logica, 67(2): 243-269.

[9]

Cadoli, M. and Schaerf, M. (1993) A survey of complexity results for nonmonotonic logics. Journal of Logic Programming, 17(2,3&4): 127-160.

[10]

Dimopoulos, Y. and Kakas, A. (1995) Logic programming without negation as failure. Proc. 5th International Symposium on Logic Programming, MIT Press, pp. 369-384.

[11]

Dowling, W. F. and Gallier, J. H. (1984) Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Journal of Logic Programming, 1(3): 267-284.

[12]

Gallo, G. and Urbani, G. (1989) Algorithms for testing the satisfiability of propositional formulae. Journal of Logic Programming, 7(1): 45-61.

Digital Library

[13]

Gottlob, G. (1992) Complexity results for nonmonotonic logics. Journal of Logic and Computation , 2: 397-425.

[14]

Governatori, G. and Maher, M. J. (2000) An argumentation-theoretic characterization of defeasible logic. Proc. European Conf. on Artificial Intelligence, IOS Press, pp. 469-474.

[15]

Grosof, B. N. (1997) Prioritized conflict handling for logic programs. Proc. Int. Logic Programming Symposium, MIT Press, pp. 197-211.

[16]

Grosof, B. N. (1999) DIPLOMAT: Business Rules Interlingua and Conflict Handling, for E-Commerce Agent Applications (Overview of System Demonstration). Proc. IJCAI-99 Workshop on Agent-mediated Electronic Commerce (AMEC-99).

[17]

Horty, J. F. (1994) Some direct theories of nonmonotonic inheritance. In: Gabbay, D. M., Hogger, C. J. and Robinson, J. A. (editors), Handbook of Logic in Artificial Intelligence and Logic Programming Vol. 3, pp. 111-187, Oxford University Press.

[18]

Horty, J. F., Thomason, R. H. and Touretzky, D. (1987) A skeptical theory of inheritance in nonmonotonic semantic networks. Proc. AAAI-87, pp. 358-363.

[19]

Kowalski, R. and Toni, F. (1996). Abstract argumentation. Artificial Intelligence and Law, 4: 275-296.

Digital Library

[20]

Maher, M. J. (2000) A denotational semantics for defeasible logic. Proc. First International Conference on Computational Logic: LNAI 1861, pp. 209-222. Springer-Verlag.

[21]

Maher, M. J., Antoniou, G. & Billington, D. (1998) A study of provability in defeasible logic. Proc. Australian Joint Conference on Artificial Intelligence: LNAI 1502, pp. 215-226. Springer-Verlag.

[22]

Maher, M. J. and Governatori, G. (1999) A semantic decomposition of defeasible logics. Proc. American National Conference on Artificial Intelligence (AAAI-99), pp. 299-305. AAAI/MIT Press.

[23]

Maher, M. J., Rock, A., Antoniou, G., Billington, D. and Miller, T. (2000) Efficient defeasible reasoning systems. Proc. Int. Conf. on Tools in Artificial Intelligence, pp. 384-392.

[24]

Miller, T. (2000) DELORES User's Manual.

[25]

Morgenstern, L. (1998) Inheritance comes of age: applying nonmonotonic techniques to problems in industry. Artificial Intelligence, 103: 1-34.

Digital Library

[26]

Niemelä, I. (1999) Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence, 25(3-4): 241-273.

Digital Library

[27]

Nute, D. (1987) Defeasible reasoning. Proc. 20th Hawaii International Conference on Systems Science, pp. 470-477. IEEE Press.

[28]

Nute, D. (1994) Defeasible logic. In: Gabbay, D. M., Hogger, C. J. and Robinson, J. A. (editors), Handbook of Logic in Artificial Intelligence and Logic Programming Vol. 3, pp. 353- 395. Oxford University Press.

[29]

Reiter, R. (1980) A logic for default reasoning. Artificial Intelligence, 13: 81-132.

Digital Library

[30]

Stein, L. A. (1992) Resolving ambiguity in nonmonotonic inheritance hierarchies. Artificial Intelligence, 55: 259-310.

Digital Library

[31]

Stillman, J. (1992) The complexity of propositional default logics. Proc. American National Conference on Artificial Intelligence (AAAI-92), pp. 794-799. AAAI/MIT Press.

[32]

Van Gelder, A., Ross, K. A. and Schlipf, J. S. (1991) The well-founded semantics for general logic programs. Journal of the ACM 38(3): 620-650.

Digital Library

Cited By

Bhuiyan HGovernatori GBond ARakotonirainy A(2024)Traffic rules compliance checking of automated vehicle maneuversArtificial Intelligence and Law10.1007/s10506-022-09340-932:1(1-56)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10506-022-09340-9
Pomarlan MHedblom MSpillner LPorzel R(2024)Revising Defeasible Theories via InstructionsRules and Reasoning10.1007/978-3-031-72407-7_13(176-190)Online publication date: 17-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72407-7_13
Fungwacharakorn WTsushima KSatoh K(2022)On Complexity and Generality of Contrary Prioritized Defeasible TheoryNew Frontiers in Artificial Intelligence10.1007/978-3-031-29168-5_2(23-35)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-29168-5_2
Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theory and Practice of Logic Programming

Theory and Practice of Logic Programming Volume 1, Issue 6

November 2001

96 pages

ISSN:1471-0684

Issue’s Table of Contents

Publisher

Cambridge University Press

United States

Publication History

Published: 01 November 2001

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bhuiyan HGovernatori GBond ARakotonirainy A(2024)Traffic rules compliance checking of automated vehicle maneuversArtificial Intelligence and Law10.1007/s10506-022-09340-932:1(1-56)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10506-022-09340-9
Pomarlan MHedblom MSpillner LPorzel R(2024)Revising Defeasible Theories via InstructionsRules and Reasoning10.1007/978-3-031-72407-7_13(176-190)Online publication date: 17-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72407-7_13
Fungwacharakorn WTsushima KSatoh K(2022)On Complexity and Generality of Contrary Prioritized Defeasible TheoryNew Frontiers in Artificial Intelligence10.1007/978-3-031-29168-5_2(23-35)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-29168-5_2
Cristani MGovernatori GOlivieri FRotolo A(2022)From Defeasible Logic to Counterfactual ReasoningRules and Reasoning10.1007/978-3-031-21541-4_5(65-80)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-21541-4_5
Governatori GOlivieri FRotolo ACristani M(2022)Inference to the Stable ExplanationsLogic Programming and Nonmonotonic Reasoning10.1007/978-3-031-15707-3_19(245-258)Online publication date: 5-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-15707-3_19
Islam MGovernatori G(2018)RuleRSArtificial Intelligence and Law10.1007/s10506-018-9218-026:4(315-344)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10506-018-9218-0
Moubaiddin ASalah IObeid N(2018)A temporal modal defeasible logic for formalizing social commitments in dialogue and argumentation modelsApplied Intelligence10.1007/s10489-017-0983-348:3(608-627)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s10489-017-0983-3
Governatori G(2018)Practical Normative Reasoning with Defeasible Deontic LogicReasoning Web. Learning, Uncertainty, Streaming, and Scalability10.1007/978-3-030-00338-8_1(1-25)Online publication date: 22-Sep-2018
https://dl.acm.org/doi/10.1007/978-3-030-00338-8_1
Cristani MOlivieri FRotolo AKeppens JGovernatori G(2017)Changes to temporary normsProceedings of the 16th edition of the International Conference on Articial Intelligence and Law10.1145/3086512.3086517(39-48)Online publication date: 12-Jun-2017
https://dl.acm.org/doi/10.1145/3086512.3086517
Kravari KBassiliades N(2016)DISARMJournal of Systems and Software10.1016/j.jss.2016.02.016117:C(130-152)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.jss.2016.02.016
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents