Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A comparison of SL- and unit-resolution search rules for stratified logic programs
Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
2010 (engelsk)Independent thesis Basic level (degree of Bachelor), 10 poäng / 15 hpOppgave
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.

sted, utgiver, år, opplag, sider
2010. , s. 70
Emneord [en]
logic programming, search rule, resolution, prolog, heuristic search
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-57363ISRN: LIU-IDA/LITH-EX-G--10/013--SEOAI: oai:DiVA.org:liu-57363DiVA, id: diva2:325247
Presentation
2010-06-08, Donald Knuth, Linköping, 20:32 (svensk)
Uppsök
Technology
Veileder
Examiner
Tilgjengelig fra: 2010-06-18 Laget: 2010-06-17 Sist oppdatert: 2018-01-12bibliografisk kontrollert

Open Access i DiVA

A comparison of SL- and unit-resolution search rules for stratified logic programs(625 kB)536 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 625 kBChecksum SHA-512
c209aa68ab283c7b87c4f1469199ede8351f9aa2985386ff64f3891086163ea14ceb73fcde7d033e87961b40e33f7a11845ef68897f21c6010e2a8ed75d526c1
Type fulltextMimetype application/pdf

Søk i DiVA

Av forfatter/redaktør
Lagerqvist, Victor
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 536 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 6908 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf