National and Kapodistrian University of Athens
Semantics of negation in extensional higher-order logic programming
Abstract
dc:descriptionWe consider the two existing extensional approaches to the semantics of positive higher-order logic programming, originally introduced by W. W. Wadge and M. Bezem respectively. The former approach uses classical domain-theoretic tools while the latter builds on a fixed-point construction defined on a syntactic instantiation of the source program. The relationships between these two approaches had not been investigated until now, while only Wadge's approach had been extended to apply to higher-order programs with negation.We show that Wadge's semantics and Bezem's semantics coincide for a broad and interesting class of programs, which do not include existentially quantified predicate variables in the bodies of clauses. We indicate that they also have profound differences, which surface when we extend our source language to allow existential predicate variables.In addition, we focus on the less developed research direction of the two, namely Bezem's semantics, and we adapt, for the first time, Bezem's technique to define an extensional semantics for higher-order logic programs with negation. For this purpose, we utilize the infinite-valued approach to negation-as-failure. On the other hand, we show that an adaptation of the technique under the well-founded or the stable model semantics does not in general lead to an extensional semantics. We analyse the reasons for this failure arguing that a three-valued setting cannot distinguish between certain predicates that appear to have a different behaviour inside a program context, but which happen to be identical as three-valued relations. As an application of our developments, we define for the first time the notions of stratification and local stratification for higher-order logic programs with negation. We prove that every stratified program has a distinguished extensional model which can be equivalently obtained through the well-founded, stable or infinite-valued model semantics. Furthermore, we show that this model does not assign the unknown truth value. These results affirm the importance and the well-behaved nature of stratified programs, which was, until now, only known for the first-order case.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2018
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Symeonidou, Ioanna
- Συμεωνίδου, Ιωάννα
Subjects
dc:subject × 10Rights
dc:rights- Statement dc:rights
-
- BY
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/44199