The intricacies of three-valued extensional semantics for higher-order logic programs. Issue 5 (23rd August 2017)

• Record Type: Journal Article
• Authors: RONDOGIANNIS, PANOS; SYMEONIDOU, IOANNA
• Editors: Rocha, Ricardo; Cao Son, Tran
• Is Part Of: Theory and practice of logic programming. Volume 17:Issue 5/6(2017)
• Page Start: 974
• Page End: 991
• Publication Date: 2017-08-23
• Subjects: Extensional higher-order logic programming, -- Negation in logic programming; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068417000357
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: M. Bezem defined an extensional semantics for positive higher-order logic programs. Recently, it was demonstrated by Rondogiannis and Symeonidou that Bezem's technique can be extended to higher-order logic programs with negation, retaining its extensional properties, provided that it is interpreted under a logic with an infinite number of truth values. Rondogiannis and Symeonidou also demonstrated that Bezem's technique, when extended under the stable model semantics, does not in general lead to extensional stable models. In this paper, we consider the problem of extending Bezem's technique under the well-founded semantics. We demonstrate that the well-founded extension fails to retain extensionality in the general case. On the positive side, we demonstrate that for stratified higher-order logic programs, extensionality is indeed achieved. We analyze the reasons of the failure of extensionality in the general case, 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.