liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Proving completeness of logic programs with the cut
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering. Polish Academic Science, Poland.ORCID iD: 0000-0002-4700-7272
2017 (English)In: Formal Aspects of Computing, ISSN 0934-5043, E-ISSN 1433-299X, Vol. 29, no 1, p. 155-172Article in journal (Refereed) Published
Abstract [en]

Completeness of a logic program means that the program produces all the answers required by its specification. The cut is an important construct of programming language Prolog. It prunes part of the search space, this may result in a loss of completeness. This paper proposes a way of proving completeness of programs with the cut. The semantics of the cut is formalized by describing how SLD-trees are pruned. A sufficient condition for completeness is presented, proved sound, and illustrated by examples.

Place, publisher, year, edition, pages
SPRINGER , 2017. Vol. 29, no 1, p. 155-172
Keywords [en]
Logic programming; The cut; Operational semantics; Program completeness; Program correctness
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-134608DOI: 10.1007/s00165-016-0392-0ISI: 000392128400007OAI: oai:DiVA.org:liu-134608DiVA, id: diva2:1075997
Available from: 2017-02-21 Created: 2017-02-21 Last updated: 2018-01-13

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Drabent, Wlodzimierz
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Formal Aspects of Computing
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 83 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf