Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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 (Engelska)Självständigt arbete på grundnivå (kandidatexamen), 10 poäng / 15 hpStudentuppsats (Examensarbete)
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.

Ort, förlag, år, upplaga, sidor
2010. , s. 70
Nyckelord [en]
logic programming, search rule, resolution, prolog, heuristic search
Nationell ämneskategori
Datavetenskap (datalogi)
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 (Svenska)
Uppsök
teknik
Handledare
Examinatorer
Tillgänglig från: 2010-06-18 Skapad: 2010-06-17 Senast uppdaterad: 2018-01-12Bibliografiskt granskad

Open Access i DiVA

A comparison of SL- and unit-resolution search rules for stratified logic programs(625 kB)535 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 625 kBChecksumma SHA-512
c209aa68ab283c7b87c4f1469199ede8351f9aa2985386ff64f3891086163ea14ceb73fcde7d033e87961b40e33f7a11845ef68897f21c6010e2a8ed75d526c1
Typ fulltextMimetyp application/pdf

Sök vidare i DiVA

Av författaren/redaktören
Lagerqvist, Victor
Av organisationen
TCSLAB - Laboratoriet för teoretisk datalogi
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 535 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 6908 träffar
RefereraExporteraLänk till posten
Permanent länk

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