Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
A comparison of SL- and unit-resolution search rules for stratified logic programs
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
2010 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

There are two symmetrical resolution rules applicable to logic programs - SL-resolution which yields a top-down refutation and unit-resolution which yields a bottom-up refutation. Both resolution principles need to be coupled with a search rule before they can be used in practice. The search rule determines in which order program clauses are used in the refutation and affects both performance, completeness and quality of solutions. The thesis surveys exhaustive and heuristic search rules for SL-resolution and transformation techniques for (general) logic programs that makes unit-resolution goal oriented.

The search rules were implemented as meta-interpreters for Prolog and were benchmarked on a suite of programs incorporating both deterministic and nondeterministic code. Whenever deemed applicable benchmark programs were permuted with respect to clause and goal ordering to see if it affected the interpreters performance and termination.

With the help of the evaluation the conclusion was that alternative search rules for SL-resolution should not be used for performance gains but can in some cases greatly improve the quality of solutions, e.g. in planning or other applications where the quality of an answer correlates with the length of the refutation. It was also established that A* is more flexible than exhaustive search rules since its behavior can be fine-tuned with weighting, and can in some cases be more efficient than both iterative deepening and breadth-first search. The bottom-up interpreter based on unit-resolution and magic transformation had several advantages over the top-down interpreters. Notably for programs where subgoals are recomputed many times. The great disparity in implementation techniques made direct performance comparisons hard however, and it is not clear if even an optimized bottom-up interpreter is competitive against a top-down interpreter with tabling of answers.

Place, publisher, year, edition, pages
2010. , 70 p.
Keyword [en]
logic programming, search rule, resolution, prolog, heuristic search
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-57363ISRN: LIU-IDA/LITH-EX-G--10/013--SEOAI: oai:DiVA.org:liu-57363DiVA: diva2:325247
Presentation
2010-06-08, Donald Knuth, Linköping, 20:32 (Swedish)
Uppsok
Technology
Supervisors
Examiners
Available from: 2010-06-18 Created: 2010-06-17 Last updated: 2010-06-28Bibliographically approved

Open Access in DiVA

A comparison of SL- and unit-resolution search rules for stratified logic programs(625 kB)474 downloads
File information
File name FULLTEXT01.pdfFile size 625 kBChecksum SHA-512
c209aa68ab283c7b87c4f1469199ede8351f9aa2985386ff64f3891086163ea14ceb73fcde7d033e87961b40e33f7a11845ef68897f21c6010e2a8ed75d526c1
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Lagerqvist, Victor
By organisation
TCSLAB - Theoretical Computer Science Laboratory
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 474 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 6621 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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