Declarative modeling of the operational behavior of logic languages
type: Item
instance of: scholarly article
title: Declarative modeling of the operational behavior of logic languages
zbMATH Open document ID: 0699.68113
DOI: 10.1016/0304-3975(89)90070-4
author: Catuscia Palamidessi
author: M. Falaschi
author: Giorgio Levi
author: M. Martelli
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
review text: A new declarative semantics for logic programs is introduced and investigated. This new semantics differs essentially from the standard van Emden-Kowalsky semantics for logic programs, allowing the presence of atoms with variables in interpretations. The latter gives possibility to model the truth of universal formulae directly and to prove a more elegant completeness theorem than the standard one. Two types of new semantics based on upwards closure and subset properties imposed on sets of atoms in interpretations are studied and compared. It is proved that both types of interpretations form complete lattices. These new semantics are shown to capture the difference between effectively computable answers and answers obtainable by instantiations of universally quantified variables. As the authors argue, this fills the gap between operational and declarative semantics existing in the standard semantics for logic programs. Counterparts of results on classical Herbrand model semantics, including existence of minimal models, fixpoint characterization, etc., are shown to hold for the new semantics. Also, a stronger versions of soundness and completeness theorems for SLD-resolution are proved. Guidelines for future research, including characterization of finite failure sets, the description of semantics for logical programs with negation and universally quantified atoms are sketched.
Mathematics Subject Classification ID: 68T15
Mathematics Subject Classification ID: 03B35
Mathematics Subject Classification ID: 68Q55
zbMATH DE Number: 4147558
zbMATH Keywords: fixpoint semantics
zbMATH Keywords: declarative semantics
zbMATH Keywords: logic programs
zbMATH Keywords: Herbrand model semantics
zbMATH Keywords: minimal models
zbMATH Keywords: SLD-resolution
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90070-4
OpenAlex ID: W2089111669
cites work: Contributions to the Theory of Logic Programming
cites work: Q3776674
cites work: The Semantics of Predicate Logic as a Programming Language
cites work: Error diagnosis in logic programming an adaptation of E.Y. Shapiro's method
cites work: Toward a declarative semantics for infinite objects in logic programming
cites work: Unit Refutations and Horn Sets
cites work: Q3716279
cites work: Q3339245
cites work: A fixpoint semantics of Horn sentences based on substitution sets
Wikidata QID: Q126310992
description: scientific article; zbMATH DE number 4147558