ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

New insights on the intuitionistic interpretation of Default Logic

Pedro Cabalar, David Lorenzo

An interesting result found by Truszczynski shows that Godel's translation of Intuitionistic Logic into S4 can also be used for encoding Default Logic (DL) into S4F. In this work we further investigate this translation showing that it preserves its utility for two general nonmonotonic formalisms: Turner's "Nested Default Logic" (NDL) and Pearce's "Equilibrium Logic" (which encodes logic programs into the intermediate logic of Here-and-There). For comparison purposes, we propose a variation of DL, we have called "Intuitionistic Default Logic" (IDL). This variation consists in replacing standard default constructs (rule conditional, justifications, disjunction in the consequent, etc) by the corresponding intuitionistic operators, using their modal interpretation in S4F. We show how both NDL and Equilibrium Logic are restricted versions of IDL, where the former does not allow nesting or combining the rule conditional operator, whereas the latter exclusively restricts the shape of classical formulas to atoms. Finally, we also study the property of "strong equivalence" for default theories -- that is, coincidence of results even under the common addition of new defaults. A simple adaptation of NDL results allows us to show that the S4F-equivalence of the modal encodings is a necessary and sufficient condition for strong equivalence.

Keywords: Nonmonotonic Reasoning, Logic Programming, Knowledge Representation

Citation: Pedro Cabalar, David Lorenzo: New insights on the intuitionistic interpretation of Default Logic. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.798-802.

[prev] [tofc] [next]

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).