Back to search

National and Kapodistrian University of Athens

Semantics of negation in extensional higher-order logic programming

Abstract

dc:description

We 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 × 10

Rights

dc:rights
Statement dc:rights
  • BY
Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/44199

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Symeonidou, Ioanna; Συμεωνίδου, Ιωάννα. Semantics of negation in extensional higher-order logic programming. National and Kapodistrian University of Athens, 2018. http://hdl.handle.net/10442/hedi/44199