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

DOI10.1016/J.TCS.2017.01.005zbMATH Open1359.68041arXiv1509.03013OpenAlexW2963286515MaRDI QIDQ512650FDOQ512650

Authors: Angelos Charalambidis, Panos Rondogiannis, Ioanna Symeonidou 

Publication date: 27 February 2017

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

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.

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

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

zbMATH Keywords

extensional higher-order logic programmingsemantics of logic programming

Mathematics Subject Classification ID

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

Cites Work

• Programming with higher-order logic.
• Title not available (Why is that?)
• Minimum model semantics for extensional higher-order logic programming with negation
• Title not available (Why is that?)
• HiLog: A foundation for higher-order logic programming
• Title not available (Why is that?)

Cited In (6)

• Extensional semantics for higher-order logic programs with negation
• Approximation fixpoint theory and the well-founded semantics of higher-order logic programs
• Title not available (Why is that?)
• The intricacies of three-valued extensional semantics for higher-order logic programs
• Equivalence of two formal semantics for functional logic programs
• Equivalence of two fixed-point semantics for definitional higher-order logic programs

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)