TY - JOUR

T1 - Set based logic programming

AU - Blair, H. A.

AU - Marek, V. W.

AU - Remmel, J. B.

N1 - Funding Information:
Acknowledgements The second author has been partly supported by NSF grants IIS-0097278 and IIS-0325063. The third author has been partly supported by NSF grants DMS 0400507 and DMS 0654060. The authors wish to thank David Jakel and Angel Rivera for contributions and valuable discussion, particularly in regard to the description of the representation of continuous functions on the real numbers.

PY - 2008/1

Y1 - 2008/1

N2 - In a previous paper (Blair et al. 2001), the authors showed that the mechanism underlying Logic Programming can be extended to handle the situation where the atoms are interpreted as subsets of a given space X. The view of a logic program as a one-step consequence operator along with the concepts of supported and stable model can be transferred to such situations. In this paper, we show that we can further extend this paradigm by creating a new one-step consequence operator by composing the old one-step consequence operator with a monotonic idempotent operator (miop) in the space of all subsets of X, 2 X . We call this extension set based logic programming. We show that such a set based formalism for logic programming naturally supports a variety of options. For example, if the underlying space has a topology, one can insist that the new one-step consequence operator always produces a closed set or always produces an open set. The flexibility inherent in the semantics of set based logic programs is due to both the range of natural choices available for specifying the semantics of negation, as well as the role of monotonic idempotent operators (miops) as parameters in the semantics. This leads to a natural type of polymorphism for logic programming, i.e. the same logic program can produce a variety of outcomes depending on the miop associated with the semantics. We develop a general framework for set based programming involving miops. Among the applications, we obtain integer-based representations of real continuous functions as stable models of a set based logic program.

AB - In a previous paper (Blair et al. 2001), the authors showed that the mechanism underlying Logic Programming can be extended to handle the situation where the atoms are interpreted as subsets of a given space X. The view of a logic program as a one-step consequence operator along with the concepts of supported and stable model can be transferred to such situations. In this paper, we show that we can further extend this paradigm by creating a new one-step consequence operator by composing the old one-step consequence operator with a monotonic idempotent operator (miop) in the space of all subsets of X, 2 X . We call this extension set based logic programming. We show that such a set based formalism for logic programming naturally supports a variety of options. For example, if the underlying space has a topology, one can insist that the new one-step consequence operator always produces a closed set or always produces an open set. The flexibility inherent in the semantics of set based logic programs is due to both the range of natural choices available for specifying the semantics of negation, as well as the role of monotonic idempotent operators (miops) as parameters in the semantics. This leads to a natural type of polymorphism for logic programming, i.e. the same logic program can produce a variety of outcomes depending on the miop associated with the semantics. We develop a general framework for set based programming involving miops. Among the applications, we obtain integer-based representations of real continuous functions as stable models of a set based logic program.

KW - Logic programming

KW - Miop-spatially augmented language

KW - Monotonic idempotent operator

KW - One-step consequence operator

UR - http://www.scopus.com/inward/record.url?scp=53649103096&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=53649103096&partnerID=8YFLogxK

U2 - 10.1007/s10472-008-9098-1

DO - 10.1007/s10472-008-9098-1

M3 - Article

AN - SCOPUS:53649103096

SN - 1012-2443

VL - 52

SP - 81

EP - 105

JO - Annals of Mathematics and Artificial Intelligence

JF - Annals of Mathematics and Artificial Intelligence

IS - 1

ER -