[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

On the intertranslatability of non-monotonic logics

Published: 10 November 1999 Publication History

Abstract

This paper concentrates on comparing the expressive powers of five nonýmonotonic logics that have appeared in the literature. For this purpose, the concept of a polynomial, faithful and modular (PFM) translation function is adopted from earlier work by Gottlob, but a weaker notion of faithfulness is proposed. The existence of a PFM translation function from one nonýmonotonic logic to another is interpreted to indicate that the latter logic is capable of expressing everything that the former logic does. Several translation functions are presented in the paper and shown to be PFM. Moreover, it is shown that PFM translation functions are impossible in certain cases, which indicates that the expressive powers of the logics involved differ strictly. The comparisons made in terms of PFM translation functions give rise to an exact classification of nonýmonotonic logics, which is then named as the expressive power hierarchy (EPH) of nonýmonotonic logics. Three syntactically restricted variants of default logic are also analyzed, and EPH is refined accordingly. Most importantly, the classes of EPH indicate some astonishing relationships in light of earlier results on the expressive power of nonýmonotonic logics presented by Gottlob as well as Bonatti and Eiter: Moore’s autoepistemic logic and prerequisiteýfree default logic are of equal expressive power and less expressive than Reiter’s default logic and Marek and Truszczyýski’s strong autoepistemic logic.

References

[1]
{1} P.A. Bonatti and T. Eiter, Querying disjunctive database through nonmonotonic logics, Theoretical Computer Science 160 (1996) 321-363.
[2]
{2} M. Cadoli, F.M. Donini and M. Schaerf, Is intractability of nonmonotonic reasoning a real drawback, Artificial Intelligence 88 (1996) 215-251.
[3]
{3} M. Cadoli and M. Lenzerini, The complexity of propositional closed world reasoning and circumscription, Journal of Computer and System Sciences 2 (1994) 255-310.
[4]
{4} T. Eiter and G. Gottlob, Propositional circumscription and extended closed world reasoning are ¿ p 2 -complete, Theoretical Computer Science 114 (1993) 231-245.
[5]
{5} J. Engelfriet, V. Marek, J. Treur and M. Truszczynski, Infinitary default logic for specification of nonmonotonic reasoning, in: Proceedings of the 5th European Workshop on Logics is Artificial Intelligence , eds. J. Alferes, L. Pereira and E. Orlowska, Lectures Notes in Artificial Intelligence, Vol. 1126 (Springer, 1996) pp. 224-236.
[6]
{6} D.W. Etherington, Formalizing nonmonotonic reasoning systems, Artificial Intelligence 31 (1987) 41-85.
[7]
{7} D.W. Etherington, Relating default logic and circumscription, in: Proceedings of the 10th International Joint Conference on Artificial Intelligence , Milan, Italy (Morgan Kaufmann, 1987) pp. 489- 494.
[8]
{8} G. Gogic, H. Kautz, C. Papadimitriou and B. Selman, The comparative linguistics of knowledge representation, in: Proceedings of the 14th International Joint Conference on Artificial Intelligence , Montreal, Canada, August 1995 (Morgan Kaufmann, 1995) pp. 862-869.
[9]
{9} G. Gottlob, Complexity results for nonmonotonic logics, Journal of Logic and Computation 2(3) (1992) 397-425.
[10]
{10} G. Gottlob, The complexity of default reasoning under the stationary fixed point semantics, Information and Computation 121 (1995) 81-92.
[11]
{11} G. Gottlob, Translating default logic into standard autoepistemic logic, Journal of the Association for Computing Machinery 42(2) (1995) 711-740.
[12]
{12} T. Imielinski, Results on translating defaults to circumscription, Artificial Intelligence 32 (1987) 131-146.
[13]
{13} T. Janhunen, Representing autoepistemic introspection in terms of default rules, in: Proceedings of the European Conference on Artificial Intelligence , Budapest, Hungary, August 1996 (Wiley, 1996) pp. 70-74.
[14]
{14} T. Janhunen, Separating disbeliefs from beliefs in autoepistemic reasoning, in: Proceedings of the 4th International Conference on Logic Programming and Non-Monotonic Reasoning , eds. J. Dix, U. Furbach and A. Nerode, Dagstuhl, Germany, July 1997, Lectures Notes in Artificial Intelligence, Vol. 1265 (Springer, 1997) pp. 132-151.
[15]
{15} T. Janhunen, Non-monotonic systems: A framework for analyzing semantics and structural properties of non-monotonic reasoning, Doctoral dissertation, Research report A49, Helsinki University of Technology, Digital Systems Laboratory, Espoo, Finland (March 1998).
[16]
{16} T. Janhunen, On the intertranslatability of autoepistemic, default and priority logics and parallel circumscription, in: Proceedings of the 6th European Workshop on Logics in Artificial Intelligence , eds. J. Dix, L. Fariñas del Cerro and U. Furbach, Dagstuhl, Germany, October 1998, Lectures Notes in Artificial Intelligence, Vol. 1489 (Springer, 1998) pp. 216-232.
[17]
{17} K. Konolige, On the relation between default and autoepistemic logic, Artificial Intelligence 35 (1988) pp. 343-382.
[18]
{18} K. Konolige, On the relation between autoepistemic logic and circumscription, in: Proceedings of the 11th International Joint Conference on Artificial Intelligence , Detroit, MI, August 1989 (Morgan Kaufmann, 1989) pp. 1213-1218.
[19]
{19} V. Lifschitz, Computing circumscription, in: Proceedings of the 9th International Joint Conference on Artificial Intelligence , Los Angeles, CA, August 1985 (Morgan Kaufmann, 1985) pp. 121-127.
[20]
{20} V. Marek, J. Treur and M. Truszczynski, Representation theory for default logic, Annals of Mathematics in Artificial Intelligence 21 (1997) 343-358.
[21]
{21} W. Marek, G.F. Shvarts and M. Truszczynski, Modal nonmonotonic logics: Ranges, characterization, computation, in: Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning , Cambridge, MA, April 1991 (Morgan Kaufmann, 1991) pp. 395-404.
[22]
{22} W. Marek and M. Truszczynski, Modal logic for default reasoning, Annals of Mathematics and Artificial Intelligence 1 (1990) pp. 275-302.
[23]
{23} W. Marek and M. Truszczynski, Nonmonotonic Logic: Context-Dependent Reasoning (Springer, Berlin, 1993).
[24]
{24} J. McCarthy, Circumscription - a form of non-monotonic reasoning, Artificial Intelligence 13 (1980) 27-39.
[25]
{25} R.C. Moore, Semantical considerations on nonmonotonic logic, in: Proceedings of the 8th International Joint Conference on Artificial Intelligence , Karlsruhe, FRG, August 1983 (Morgan Kaufmann, 1983) pp. 272-279.
[26]
{26} I. Niemelä, Towards automatic autoepistemic reasoning, in: Proceedings of the European Workshop on Logics in Artificial Intelligence - JELIA'90 , Amsterdam, The Netherlands, September 1990 (Springer, 1990) pp. 428-443.
[27]
{27} I. Niemelä, On the decidability and complexity of autoepistemic reasoning, Fundamenta Informaticae 17(1,2) (1992) 117-155.
[28]
{28} I. Niemelä, A unifying framework for nonmonotonic reasoning, in: Proceedings of the 10th European Conference on Artificial Intelligence , Vienna, Austria, August 1992 (Wiley, 1992) pp. 334-338.
[29]
{29} I. Niemelä, Autoepistemic logic as a unified basis for nonmonotonic reasoning, Doctoral dissertation, Research report A24, Digital Systems Laboratory, Helsinki University of Technology, Espoo, Finland (August 1993).
[30]
{30} I. Niemelä, Implementing circumscription using a tableau method, in: Proceedings of the European Conference on Artificial Intelligence , Budapest, Hungary, August 1996 (Wiley, 1996) pp. 80-84.
[31]
{31} R. Reiter, A logic for default reasoning, Artificial Intelligence 13 (1980) 81-132.
[32]
{32} G. Schwarz, On embedding default logic into Moore's autoepistemic logic, Artificial Intelligence 80 (1996) 349-359.
[33]
{33} J. Stillman, It's not my default: the complexity of membership problems in restricted propositional default logics, in: Proceedings of the 8th National Conference on Artificial Intelligence , Boston, MA, July 1990 (MIT Press, Cambridge, MA, 1990) pp. 571-578.
[34]
{34} L. Stockmeyer, The polynomial-time hierarchy, Theoretical Computer Science 3 (1977) 1-22.
[35]
{35} L. Stockmeyer, Classifying the computational complexity of problems, Journal of Symbolic Logic 52(1) (1987) 1-43.
[36]
{36} M. Truszczynski, Modal interpretations of default logic, in: Proceedings of the 12th International Joint Conference on Artificial Intelligence , Sydney, Australia, August 1991 (Morgan Kaufmann, 1991) pp. 393-398.
[37]
{37} X. Wang, J.-H. You and L.Y. Yuan, Nonmonotonic reasoning by monotonic inferences with priority constraints, in: Proceedings of the 2nd International Workshop on Non-Monotonic Extensions of Logic Programming , Lecture Notes in Artificial Intelligence, Vol. 1216 (Springer, 1996) pp. 91-109.

Cited By

View all
  • (2024)Strong Backdoors for Default LogicACM Transactions on Computational Logic10.1145/365502425:3(1-24)Online publication date: 30-Mar-2024
  • (2023)Default logic as a species of causal reasoningProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2023/12(117-126)Online publication date: 2-Sep-2023
  • (2017)On the equivalence between assumption-based argumentation and logic programmingJournal of Artificial Intelligence Research10.5555/3207692.320771060:1(779-825)Online publication date: 1-Sep-2017
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Annals of Mathematics and Artificial Intelligence
Annals of Mathematics and Artificial Intelligence  Volume 27, Issue 1-4
1999
197 pages

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 10 November 1999

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Strong Backdoors for Default LogicACM Transactions on Computational Logic10.1145/365502425:3(1-24)Online publication date: 30-Mar-2024
  • (2023)Default logic as a species of causal reasoningProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2023/12(117-126)Online publication date: 2-Sep-2023
  • (2017)On the equivalence between assumption-based argumentation and logic programmingJournal of Artificial Intelligence Research10.5555/3207692.320771060:1(779-825)Online publication date: 1-Sep-2017
  • (2012)The Complexity of Reasoning for Fragments of Autoepistemic LogicACM Transactions on Computational Logic10.1145/2159531.215953913:2(1-22)Online publication date: 1-Apr-2012
  • (2012)Uniform evaluation of nonmonotonic DL-ProgramsProceedings of the 7th international conference on Foundations of Information and Knowledge Systems10.1007/978-3-642-28472-4_1(1-22)Online publication date: 5-Mar-2012
  • (2011)On the intertranslatability of argumentation semanticsJournal of Artificial Intelligence Research10.5555/2051237.205125141:2(445-475)Online publication date: 1-May-2011
  • (2011)Embedding nonground logic programs into autoepistemic logic for knowledge-base combinationACM Transactions on Computational Logic10.1145/1929954.192995712:3(1-39)Online publication date: 16-May-2011
  • (2009)The complexity of circumscription in description logicJournal of Artificial Intelligence Research10.5555/1641503.164152035:1(717-773)Online publication date: 1-Aug-2009
  • (2008)Embedding approaches to combining rules and ontologies into autoepistemic logicProceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning10.5555/3031661.3031719(485-495)Online publication date: 16-Sep-2008
  • (2008)First-Order Ground Non-Monotonic Modal LogicFundamenta Informaticae10.5555/2365280.236528283:3(253-276)Online publication date: 1-Aug-2008
  • Show More Cited By

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media