Equivalence of two fixed-point semantics for definitional higher-order logic programs

DOI10.1016/J.TCS.2017.01.005MaRDI QIDQ512650zbMATH OpenOpenAlexFDO

Authors Angelos Charalambidis, Panos Rondogiannis, Ioanna Symeonidou

Publication date 27 February 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.03013

zbMATH Keywords

extensional higher-order logic programmingsemantics of logic programming

Mathematics Subject Classification ID

Logic programming (68N17) Semantics in the theory of computing (68Q55)

Abstract: Two distinct research approaches have been proposed for assigning a purely extensional semantics to higher-order logic programming. 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. In this paper we demonstrate that for a very broad class of programs, namely the class of definitional programs introduced by W. W. Wadge, the two approaches coincide (with respect to ground atoms that involve symbols of the program). On the other hand, we argue that if existential higher-order variables are allowed to appear in the bodies of program rules, the two approaches are in general different. The results of the paper contribute to a better understanding of the semantics of higher-order logic programming.

Recommendations

• Equivalence of two fixed-point semantics for definitional higher-order logic programs
• Equivalence of two formal semantics for functional logic programs
• Approximation fixpoint theory and the well-founded semantics of higher-order logic programs
• On the equivalence of semantics for normal logic programs
• scientific article; zbMATH DE number 3956409
• Equivalences among logics of programs
• Strong equivalence of logic programs under the infinite-valued semantics
• Fixpoint semantics for logic programming a survey
• scientific article; zbMATH DE number 3846863

Cites work

• scientific article; zbMATH DE number 43398 (Why is no real title available?)
• scientific article; zbMATH DE number 1158760 (Why is no real title available?)
• scientific article; zbMATH DE number 1841821 (Why is no real title available?)
• HiLog: A foundation for higher-order logic programming
• Minimum model semantics for extensional higher-order logic programming with negation
• Programming with higher-order logic.

Cited in

(5)

• Approximation fixpoint theory and the well-founded semantics of higher-order logic programs
• Equivalence of two formal semantics for functional logic programs
• scientific article; zbMATH DE number 7023675 (Why is no real title available?)
• Equivalence of two fixed-point semantics for definitional higher-order logic programs
• The intricacies of three-valued extensional semantics for higher-order logic programs

Describes a project that uses

Uses Software

• HiLog

This page was built for publication: Equivalence of two fixed-point semantics for definitional higher-order logic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q512650)