Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-21T23:19:22.714Z Has data issue: false hasContentIssue false

Applications of intuitionistic logic in Answer Set Programming

Published online by Cambridge University Press:  16 April 2004

MAURICIO OSORIO
Affiliation:
Universidad de las Américas, CENTIA, Sta. Catarina Mártir, Cholula, Puebla, 72820 México (e-mail: [email protected])
JUAN A. NAVARRO
Affiliation:
Universidad de las Américas, CENTIA, Sta. Catarina Mártir, Cholula, Puebla, 72820 México
JOSÉ ARRAZOLA
Affiliation:
Universidad de las Américas, CENTIA, Sta. Catarina Mártir, Cholula, Puebla, 72820 México

Abstract

We present some applications of intermediate logics in the field of Answer Set Programming (ASP). A brief, but comprehensive introduction to the answer set semantics, intuitionistic and other intermediate logics is given. Some equivalence notions and their applications are discussed. Some results on intermediate logics are shown, and applied later to prove properties of answer sets. A characterization of answer sets for logic programs with nested expressions is provided in terms of intuitionistic provability, generalizing a recent result given by Pearce. It is known that the answer set semantics for logic programs with nested expressions may select non-minimal models. Minimal models can be very important in some applications, therefore we studied them; in particular we obtain a characterization, in terms of intuitionistic logic, of answer sets which are also minimal models. We show that the logic G3 characterizes the notion of strong equivalence between programs under the semantic induced by these models. Finally we discuss possible applications and consequences of our results. They clearly state interesting links between ASP and intermediate logics, which might bring research in these two areas together.

Type
Regular Papers
Copyright
© 2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)